Friday, May 23, 2014

Reporting infeasible LP solutions in GAMS

When debugging models, one strategy that can be very helpful: fix a number of variables to a known (feasible) solution, solve, and inspect the reported infeasibilities. The known solution can be complete or can be a partial solution (i.e. only a fraction of the variables is fixed). In GAMS this can be done with statements like:

   x.fx(i,j) = solutionx(i,j);
   solve m using lp minimizing z;

The infeasibilities are reported in the solution report in the listing file.
Unfortunately not all solvers support this. Here is a small sample:
  • MINOS: ok
  • BDMLP: ok
  • Cplex: ok
  • Gurobi: no solution reported so nothing to look at
  • Mosek: not a normal solution reported 
  • Lindo: no solution reported
  • Xpress: no solution reported
  • CBC: no solution reported
This is not a pretty list. All older GAMS solvers do a good job and provide the wanted information without a problem, but the newer solvers and links do a rather poor job on helping me out. 

1 comment:

  1. To me it seems you argue that the optimizers should report the optimal solution to the phase 1 problem. Are you aware that at least all commercial interior-point optimizers does not use a phase 1 and phase 2 approach as thought in textbooks. Hence they will report not a solution to the phase 1 problem. Secondly the introduction of presolve has made it hard to report a solution to the phase 1 problem.
    In any case the phase 1 problem is not unique thing so asking for solution to a phase problem is somewhat strange.

    There is one thing that is unique if the problem is infeasible and that is Farkas type certificate of the infeasiblity. Usually the Farkas ceriticate is exactly the information you need to move on because unless you change the model to invalidate the certificate the model will stay infeasible.
    See my note http://docs.mosek.com/whitepapers/infeas.pdf.

    So I will argue the right question to ask from the optimizers is: Which of the optimizers provide me a Farkas certificate of the infeasibility?

    PS: Note in MOSEK you will always get a Farkas certificate independent of the algorithm employed (simplex or interior-point) and whether presolve is turned on or off. I would like to see the argument for that it is strange way to treat infeasible problem.

    ReplyDelete