I get this question a lot. The smallest example is model number 1 from the GAMS model library [1]: a tiny transportation model (originally from [2]). The linear programming (LP) model looks like:
| \[\begin{align} \min \>&z \\ &z = \sum_{i,j} c_{i,j} x_{i,j}&&\text{(cost)}\\ &\sum_j x_{i,j} \le a_i \>\forall i &&\text{(supply)}\\ &\sum_i x_{i,j} \ge b_j \>\forall j &&\text{(demand)}\\ &x_{i,j} \ge 0 \end{align}\] |
The model has only two source nodes and three destination nodes and the solution looks like:
LOWER LEVEL UPPER MARGINAL ---- EQU cost . . . 1.0000 cost define objective function ---- EQU supply observe supply limit at plant i LOWER LEVEL UPPER MARGINAL seattle -INF 350.0000 350.0000 EPS ---- EQU demand satisfy demand at market j LOWER LEVEL UPPER MARGINAL new-york 325.0000 325.0000 +INF 0.2250 ---- VAR x shipment quantities in cases LOWER LEVEL UPPER MARGINAL seattle .new-york . 50.0000 +INF . LOWER LEVEL UPPER MARGINAL ---- VAR z -INF 153.6750 +INF . z total transportation costs in thousands of dollars |
There are quite a few things to say about this solution listing.
There are 6 equations in this model and 7 variables. The objective function is modeled as an equality here as GAMS does not really have the notion of an objective function: it has an objective variable. The objective variable \(z\) is a free variable i.e. it has bounds \(-\infty\) and \(\infty\). This is also a GAMS convention.
The dots indicate a zero value. In the cost equation we can see the lower- and upper-bound are the same (both zero) indicating an equality. Note that this equation is rewritten as \(z - \sum_{i,j} c_{i,j} x_{i,j} = 0\) hence the bounds having a zero value.
The column marked MARGINAL are duals (for the rows) and reduced costs for the variables.
The row SUPPLY(‘SEATTLE’) has a marginal with a value of EPS. This means: this row is non-basic but with a zero dual. The EPS is used to signal this is a non-basic row: it the value was zero we could have deduced the row is basic. All basic rows and variables have a marginal that is zero. To verify we can count the basic and non-basic variables:
ROW/COLUMN MARGINAL BASIS-STATUS cost 1.000 NB |
All the variables and rows that have a marginal of zero are basic. There are 6 of them. This is identical to the number of equations. This conforms to what we would expect. The other 7 rows and columns have a non-zero marginal and are non-basic.
The occurrence of an EPS in the marginals indicates dual degeneracy. This indicates there are multiple optimal solutions (to be precise: multiple optimal bases). Indeed here is an alternative solution found with a different LP solver:
LOWER LEVEL UPPER MARGINAL ---- EQU cost . . . 1.0000 cost define objective function ---- EQU supply observe supply limit at plant i LOWER LEVEL UPPER MARGINAL seattle -INF 300.0000 350.0000 . ---- EQU demand satisfy demand at market j LOWER LEVEL UPPER MARGINAL new-york 325.0000 325.0000 +INF 0.2250 ---- VAR x shipment quantities in cases LOWER LEVEL UPPER MARGINAL seattle .new-york . . +INF EPS LOWER LEVEL UPPER MARGINAL ---- VAR z -INF 153.6750 +INF . z total transportation costs in thousands of dollars |
The term primal degeneracy is used to indicate that a basic row or column is at its bound (usually they are in between bounds). We see an example of that in row SUPPLY(‘SEATTLE’) here: this row is basic but the value 600 is equal to the upper bound. This solution is also dual degenerate: we have an EPS marginal for variable X(‘SEATTLE’,’NEW-YORK’).
Notes
Q: Can we enumerate all possible optimal solutions? Not so easy, but in [3] an interesting approach is demonstrated on this model.
Q: Can we make \(z\) a positive variable? Well, GAMS is not very consistent here.
You can not declare ‘positive variable z’ as GAMS will complain: Objective variable is not a free variable. But we can assign: ‘z.lo = 0;’. Don’t ask me why. In general I just keep the variable unbounded.
Q: Can we use ranged equations in GAMS? No.
The listing file seems to indicate we can set lower and upper-bounds on rows. But this is not really true. If you would assign values say ‘supply.up(i) = INF;’, GAMS will ignore this and reset the bounds on the equations when generating the model.
Q: What about NLPs? Roughly the same. There is one major deviation: NLP solutions typically contain superbasic variables. These are non-basic (i.e. with a nonzero marginal) but are between their bounds.
Q: What about MIPs? By default GAMS will do the following after a MIP terminates: fix all discrete variables to their current level and resolve as an LP. So you will see marginals from this final LP. Marginals for a real MIP do not really exist (MIP nodes solved by say a dual simplex method have typically a number of discrete variables fixed by the branch-and-bound methods, cuts are added and heuristics are used also by modern MIP solvers).
Q: Can a free variable be non-basic? In almost all cases a free variable in an LP solution will be basic (a free basic variable will in general never leave the basis). However, it is possible for such a variable to be non-basic in which case it is usually zero.
Q: Why do we need this EPS? The purpose of this EPS thing is to allow GAMS to set up an advanced basis for subsequent solves. These subsequent solves will typically be faster when we use an advanced basis. This method is solver independent. E.g. to make Gurobi look good we can do:
option lp=cplex;
solve m using lp minimizing z;
option lp=gurobi;
solve m using lp minimizing z;
This even works with different models that share many variables and equations:
option lp=cplex;
solve m1 using lp minimizing z1;
option nlp=minos;
solve m2 using nlp minimizing z2;
Q: My solver does not have a basis-preserving presolve, so I have to choose between presolving and using an advanced basis. Yes, unfortunately that is much the case with modern solvers. You need to make a decision here, hopefully after doing some tests. If the restarts solve very fast (i.e. need few iterations), usually bypassing the presolver is not a big deal.
Q: What is the meaning of a marginal when the model is infeasible. I am not sure. Are they wrt to a Phase I, Phase 2 or some composite objective? I would say: this is not well-defined.
Q: Any other uses for EPS? Yes. GAMS stores everything in a sparse format so all zeros are not stored (the exception is a scalar which is stored even if zero). When exporting data sometimes we want explicit zeros to be exported. An example is to prevent a matrix to miss a row or column that has only zeros. We can assign an EPS for these cases. Many tools like GDXXRW or GDX2SQLITE can convert EPS values to physical 0.0 values.
References
- https://www.gams.com/latest/gamslib_ml/libhtml/gamslib_trnsport.html
- Dantzig, G. B., Linear Programming and Extensions. Princeton University Press, Princeton, New Jersey, 1963.
- http://yetanothermathprogrammingconsultant.blogspot.com/2016/01/finding-all-optimal-lp-solutions.html
No comments:
Post a Comment