Monday, September 4, 2017

What is this EPS in a GAMS solution?

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        
san-diego        -INF          550.0000       600.0000          .         

---- EQU demand  satisfy demand at market j

                LOWER          LEVEL          UPPER         MARGINAL

new-york       325.0000       325.0000        +INF            0.2250     
chicago        300.0000       300.0000        +INF            0.1530     
topeka         275.0000       275.0000        +INF            0.1260     

---- VAR x  shipment quantities in cases

                          LOWER          LEVEL          UPPER         MARGINAL

seattle  .new-york          .            50.0000        +INF             .         
seattle  .chicago           .           300.0000        +INF             .         
seattle  .topeka            .              .            +INF            0.0360     
san-diego.new-york          .           275.0000        +INF             .         
san-diego.chicago           .              .            +INF            0.0090     
san-diego.topeka            .           275.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
supply('seattle')                EPS         NB
supply('san-diego')              .           B
demand('new-york')             0.2250        NB
demand('chicago')              0.1530        NB
demand('topeka')               0.1260        NB
x('seattle','new-york')          .           B
x('seattle','chicago')           .           B
x('seattle','topeka')          0.0360        NB
x('san-diego','new-york')        .           B
x('san-diego','chicago')       0.0090        NB
x('san-diego','topeka')          .           B
z                                .           B

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          .         
san-diego        -INF          600.0000       600.0000          .         

---- EQU demand  satisfy demand at market j

                LOWER          LEVEL          UPPER         MARGINAL

new-york       325.0000       325.0000        +INF            0.2250     
chicago        300.0000       300.0000        +INF            0.1530     
topeka         275.0000       275.0000        +INF            0.1260     

---- VAR x  shipment quantities in cases

                          LOWER          LEVEL          UPPER         MARGINAL

seattle  .new-york          .              .            +INF            EPS        
seattle  .chicago           .           300.0000        +INF             .         
seattle  .topeka            .              .            +INF            0.0360     
san-diego.new-york          .           325.0000        +INF             .         
san-diego.chicago           .              .            +INF            0.0090     
san-diego.topeka            .           275.0000        +INF             .         

                           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
  1. https://www.gams.com/latest/gamslib_ml/libhtml/gamslib_trnsport.html
  2. Dantzig, G. B., Linear Programming and Extensions. Princeton University Press, Princeton, New Jersey, 1963.
  3. http://yetanothermathprogrammingconsultant.blogspot.com/2016/01/finding-all-optimal-lp-solutions.html

No comments:

Post a Comment