Tuesday, June 17, 2014

What NOT to do when an optimization problem is infeasible!

Given your optimization problem is infeasible then what should do?

A common practice is to look at the infeasible solution returned by the optimizer e.g. MOSEK and then relax the bounds that are violated by the reported solution. This practice is rooted in the fact that in the good old days all linear optimization problems was optimized using the primal simplex algorithm employing a phase 1 and phase 2 approach as described in textbooks. The purpose of the phase 1 is to find a feasible solution and then in phase 2 to locate an optimal solution starting from the phase 1 solution. The implication is if no feasible solution exists, then the reported solution will be as close to as feasible solution as possible in a well defined sense. Therefore, it make sense to relax the problem based on the solution reported by the phase 1 because that leads to the smallest possible relaxation that make the problem feasible.

However, nowadays this does not work in most cases for the following reasons:
  1. Most optimizers apply a presolve to the problem before optimizing. Now finding an optimal phase 1 solution to the presolved problem is almost never the same as finding an optimal phase 1 solution to the original problem  if the problem is infeasible. Therefore, if the presolve has been effective the reported solution is likely to be far from an optimal phase 1 solution to the original problem.
  2. Moreover, if the problem is found to be infeasible during the presolve, then the phase 1 problem is not solved at all and hence the optimal solution to the phase 1 problem is not available.  
  3. Interior-point based optimizers does not use a phase 1 and phase 2 approach, Therefore, the primal solution returned by an interior-point optimizer for infeasible problems is usually not very informative and definitely not close to an optimal solution to a phase 1 problem.
  4. The dual simplex algorithm never solves the phase 1 problem. Rather in case of an infeasible problem it produce a Farkas certificate of the infeasibility.  
The main recomodation is if an optimization problem is diagnosed infeasible by an optimizer e.g. MOSEK, then do NOT use the primal solution for anything unless you are absolutely sure it is an optimal solution to a phase 1 problem. 

Then what should you do? Assuming the problem is a continuous linear or convex optimization problem then there is a so called Farkas certificate that proves the problem is infeasible. Some optimizes like MOSEK will report the Farkas certificate as the dual solution. Such a Farkas certificate can be used to repair the problem as discussed in the technical report.  

Alternatively a phase 1 problem can be formed explicitly and solved if you want to do the traditional repair procedure. By the way the optimal dual solution to the phase 1 problem will be a Farkas certificate of the infeasible status. Hence, the phase 1 problem can seen as computing a Farkas certificate if one is available.