Drawback Assertion
The issue assertion is given under. x and y are the 2 choice variables. The target is to maximise revenue topic to a few constraints. Each x and y have decrease and higher bounds respectively.
Revenue = 90x + 75y
Goal: maximize Revenue topic to:
3x+2y≤66
9x+4y≤180
2x+10y≤200Bounds:
2≤x≤8
10≤y≤40
Optimization utilizing highspy
Within the code under, I provoke the mannequin as h. Then, I introduce my choice variables x and y together with their decrease bounds and higher bounds respectively, and likewise assign the names. Subsequent, I add the three constraint inequalities which I’ve known as c0, c1 and c2 respectively. Every constraint has coefficient for x and y, and a RHS worth. Then, I maximized the worth of 90x+75y, which is the target perform. The mannequin is run on this line.
import highspy
import numpy as np#provoke the mannequin
h = highspy.Highs()
#outline choice variables
x = h.addVariable(lb = 2, ub = 8, identify = “x”)
y = h.addVariable(lb = 10, ub = 40, identify = “y”)
#h.setOptionValue("solver", "ipm")
#outline constraints
h.addConstr(3*x + 2*y<=66) #c0
h.addConstr(9*x + 4*y<=180) #c1
h.addConstr(2*x + 10*y<=200) #c2
#goal
h.maximize(90*x + 75*y)
What occurs within the backend throughout the optimization course of?
When the mannequin runs, one can see the next progress taking place within the terminal window. However what precisely is occurring right here? I describe it under:
Drawback dimension:
The constraints within the linear downside might be represented within the matrix kind as Ax≤b, whereby, A is the matrix of constraint coefficients, x is the vector containing choice variables, and b is the matrix of RHS values. For the given downside, the constraints are represented within the matrix format as proven under:
The issue matrix dimension is characterised by rows, columns and non-zero components. Row refers back to the variety of constraints (right here 3), column refers back to the variety of choice variables (right here 2), and components/non-zeros seek advice from the coefficients, which don’t have zero values. In all three constraints, there are not any coefficient with zero worth. Therefore the entire variety of non-zero components is six.
That is an instance of a quite simple downside. In actuality, there might be issues the place the variety of rows, columns and non-zero components might be within the order of 1000’s and hundreds of thousands. A rise in the issue dimension will increase the complexity of the mannequin, and the time taken to unravel it.
Coefficient ranges
The coefficients of x and y in the issue vary from 2 to 10. Therefore, the matrix coefficient vary is displayed as [2e+00, 1e+01].
Value refers back to the goal perform right here. Its coefficient is 90 for x and 75 for y. In consequence, Value has a coefficient vary of [8e+01, 9e+01].
Bounds for x and y vary between 2 and 40. Therefore, Sure has a coefficient vary of [2e+00, 4e+01]
Coefficients of RHS vary between 66 and 200. Therefore, RHS has a coefficient vary of [7e+01, 2e+02].
Presolving
Presolve is the preliminary course of when a solver tries to unravel an optimization downside, it tries to simplify the mannequin at first. For instance, it would deal with a coefficient past a sure worth as infinity. The aim of the presolve is to create a smaller model of the issue matrix, with an identical goal perform and with a possible house that may be mapped to the possible house of the unique downside. The decreased downside matrix could be easier, simpler, and sooner to unravel than the unique one.
On this case, the presolve step was accomplished in simply two iterations leading to an empty matrix. This additionally implies that the answer was obtained and no additional optimization was required. The target worth it returned was 2100, and the run time of the HiGHS solver was simply 0.01 seconds. After the answer is obtained from the optimization, the solver can use the postsolve/unpresolve step whereby, the answer is mapped to the possible house of the unique downside.
Mathematical Programming System (MPS) format
Mathematical Programming System (MPS) is a file format for representing linear and blended integer linear programming issues. It’s a comparatively outdated format however accepted by all industrial linear program solvers. Linear issues will also be written in different codecs resembling LP, AMPL, and GAMS.
One can use highspy to put in writing mps file by merely utilizing h.writeModel("foo.mps"). And studying the mps file is so simple as h.readModel("foo.mps").
The construction of the MPS file of the given optimization downside is proven above. It begins with the NAME of the LP downside. OBJSENSE signifies whether or not the issue is a minimization (MIN) or maximization (MAX), right here the latter. The ROWS part signifies the target, names of all constraints, and their sorts when it comes to equality/inequality. E stands for equality, G stands for larger than or equal rows, L stands for lower than or equal rows, and N stands for no restriction rows. Right here, the three constraints are given as __c0, __c1, and __c2 whereas Obj is the abbreviation for the target.
Within the COLUMNS part, the names of the choice variables (right here x and y) are assigned on the left, and their coefficients which belong to goal or constraints inequalities are supplied on the proper. The RHS part accommodates the right-hand facet vectors of the mannequin constraints. The decrease and higher bounds of the choice variables are outlined within the BOUNDS part. The MPS file closes with ENDATA.
Optimization Course of and Getting Outcomes
HiGHS makes use of algorithms resembling simplex or inside level technique for the optimization course of. To elucidate these algorithms deserve a separate publish of their very own. I hope to the touch upon them sooner or later.
The code used to extract the outcomes is given under. The mannequin standing is optimum. I extract the target perform worth and the answer values of the choice variables. Moreover, I print the variety of iterations, the standing of primal and twin options, and foundation validity.
resolution = h.getSolution()
foundation = h.getBasis()
data = h.getInfo()model_status = h.getModelStatus()
print("Mannequin standing = ", h.modelStatusToString(model_status))
print()
#Get resolution goal worth, and optimum values for x and y
print("Optimum goal = ", data.objective_function_value)
print ("Optimum worth of x:", resolution.col_value[0])
print ("Optimum worth of y:", resolution.col_value[1])
#get mannequin run traits
print('Iteration depend = ', data.simplex_iteration_count)
print('Primal resolution standing = ', h.solutionStatusToString(data.primal_solution_status))
print('Twin resolution standing = ', h.solutionStatusToString(data.dual_solution_status))
print('Foundation validity = ', h.basisValidityToString(data.basis_validity))
Answer Recordsdata
After the optimization course of, HiGHS permits writing the answer into an answer file with a .sol extension. Additional, the answer might be written in several codecs as given right here. 1 stands for HiGHS fairly format, and three stands for Glpsol fairly format respectively.
To get the answer in fashion 3, I used h.writeSolution("mysolution.sol", 3). The issue statistics are supplied on the high. The optimum resolution values are supplied within the Exercise column. The St column specifies the standing of the answer. For instance, B stands for Primary- the variable or constraint is a part of the premise resolution (optimum). NU refers that the answer is non-basic and is identical because the higher certain. The worth within the Marginal column (also known as the shadow value or twin worth) refers to how a lot the target perform would range with the unit change within the non-basic variable. For extra data on the GLPK resolution file data, one can seek advice from right here.
Conclusion
On this publish, I offered an instance of fixing a easy linear optimization downside utilizing an open-source solver referred to as HiGHS with the highspy package deal in Python. Subsequent, I defined how the optimization downside dimension might be inferred utilizing the coefficient matrix, choice variable vector and RHS vector. I launched and defined totally different parts of mathematical programming system (mps) information for representing optimization downside. Lastly, I demonstrated the optimization means of a solver, steps for extracting outcomes and analyzing the answer file.
The pocket book and related information for this publish is obtainable on this GitHub repository. Thanks for studying!