Repairing MIP infeasibility through local branching

摘要

Finding a feasible solution to a generic mixed-integer linear program (MIP) is often a very difficult task. Recently, two heuristic approaches called feasibility pump and local branching have been proposed to address the problem of finding a feasible solution and improving it, respectively. In this paper we introduce and analyze computationally a hybrid algorithm that uses the feasibility pump method to provide, at very low computational cost, an initial (possibly infeasible) solution to the local branching procedure. The overall procedure is reminiscent of Phase I of the two phase simplex algorithm, in which the original LP is augmented with artificial variables that make a known infeasible starting solution feasible and then the augmented model is solved to iteratively reduce that infeasibility by driving the values of the artificial variables to zero. As such, our approach can also to used to find (heuristically) a minimum-cardinality set of constraints whose removal converts an infeasible MIP into a feasible one—a very important piece of information in the analysis of infeasible MIP models. Often, in practical applications finding a good feasible solution is the main order of business. At this purpose, local search methods generally start by a feasible solution and eventually improve it until a fixed point is reached and the algorithm is aborted. Sometimes, however, finding such a first feasible solution is hard and can be unnecessary since an initial slightly infeasible solution can be repaired to become feasible and eventually improved. We propose to integrate in the above spirit two recent algorithms for general-purpose MIPs—namely feasibility pump and local branching—which were originally proposed to separately cope with the issues of finding an initial feasible solution and improve it.