Column Elimination for Large-Scale Integer Programming
Poster, IPCO, Madison, Wisconsin
Branch-and-cut-and-price is a state-of-the-art exact method for solving large- scale integer programming models, using column generation to solve linear programming relaxations of its subproblems. Column generation maintains a restricted set of variables and iteratively adds new variables by solving a pricing problem until an optimal basis is found. Recently, a new method has been developed that solves large- scale integer programming problems using branch-and-cut, that directly solves an arc flow formulation instead of solving pricing problems. This new method maintains a relaxed set of variables and iteratively removes infeasible variables until an optimal solution to the relaxation is feasible to the original problem. The method has been used for specific applications, but not yet generalized. In this poster, we generalize this method to solve discrete optimization problems under the name column elimination. We give methodological insights including computational efficiencies and show promising experimental results on applications including the vehicle routing problem with time windows for which column elimination has not yet been applied.