Is the simplex algorithm the most important algorithm for solving linear programs (LPs)? If you pose this question to a mathematical optimization expert, you will most likely get a "Yes, but..." as a reply. It is common folklore in the field that simplex is the most viable choice for solving sequences of similar LPs, like a mixed integer programming (MIP) solver does. The "but..." is brought in by the barrier algorithm. Barrier is on average faster for solving a single LP and it has the nice theoretical property of a polynomial runtime. Still, the common conception is that MIP solvers hardly benefit from the barrier algorithm and the best academic MIP solvers do not even include one. Most commercial solvers, however, use barrier as part of a concurrent solve of the initial LP relaxation, which gives some performance benefits. We at FICO Xpress recently added some more applications of barrier to our MIP solver.
A barrier solution provides some unique structural insight into the problem at hand. This is due to the fact that barrier provides a solution which is in the relative interior of the optimal set – or the feasible set when run without an objective function. The latter is typically referred to as the analytic center solution. A variable taking a value at its bound or close to its bound in the analytic center tells you something about the likelihood that this variable takes the bound value in a feasible MIP solution.
We exploit the analytic center in different ways:
- Presolving: If a variable is exactly at its bound in the analytic center (which is in the relative interior), then this is an indirect proof that this variable will be at its bound in every LP solution. Thus, it can be fixed in presolving.
- Primal Heuristic: The analytic center can be seen as an indicator for the direction into which a variable is likely to move when going towards feasibility. We therefore use it as an auxiliary objective to search for a first feasible solution on particularly hard MIPs.
- Branching: For the same reason, we use the analytic center to take branching decisions on the first levels of branch-and-bound on extremely dual degenerate MIP problems.
Last week, we presented these developments at the Operations Research Conference 2017 in Berlin, Germany. We submitted a paper to the post-conference proceedings, find it here:
Within FICO Xpress, the proposed presolving, heuristic, and branching strategy all improve performance, but come with the computational burden of having to compute the barrier solution first. For each of the individual procedures, this is a rather big overhead. However, the barrier solution only needs to be computed once to enable the application of all of them, thus it is the variety of applications that makes it worthwhile. There are certainly more possible applications of barrier solutions within MIP solving, like for cutting plane generation, cut filtering, node selection or diverse primal heuristics. We would be excited to see further research in this direction.
You can learn more about FICO Xpress Optimization, ask questions, and hear from experts in the Optimization Community.