Column Elimination: An Iterative Approach to Solving Integer Programs.

We present column elimination as a general framework for solving integer programming problems. Problems are represented using an arc flow formulation where solutions are compactly represented as paths in a directed acyclic graph. The column elimination method begins with a relaxed representation, which may include infeasible paths, and solves a constrained network flow over the graph to identify a solution. It then iteratively refines the graph by eliminating infeasible paths until an optimal feasible solution is found. We introduce a subgradient method for solving the Lagrangian relaxation of the problem, which offers additional opportunities for graph refinement. We demonstrate the effectiveness of this approach on three applications: the graph multicoloring problem, the vehicle routing problem with time windows, and the pickup-and-delivery problem with time windows. On each of these domains, column elimination closes open benchmark instances. 

This is joint work with Anthony Karahalios.

About Willem-Jan

Willem-Jan van Hoeve is the Carnegie Bosch Professor of Operations Research at the Tepper School of Business, Carnegie Mellon University. His research focuses on developing new methodologies for mathematical optimization with applications to network design, scheduling, vehicle routing, data mining, and others. He made notable contributions to the areas of constraint and integer programming, and most recently pioneered the field of decision diagrams for optimization. Van Hoeve’s research has been funded by the National Science Foundation, the Office of Naval Research, and two Google Faculty Research Awards. He has consulted for a variety of companies including FedEx Ground, Exxon Mobil, PNC Bank, Bosch/Siemens, and Charter Steel, as well as a number of non-profit organizations. Van Hoeve is the recipient of the INFORMS Computing Society Harvey J. Greenberg Research Award, the Tepper School’s MBA Teaching Award (twice) and MSBA Teaching Award, and several best paper awards. He is currently Associate Editor for the INFORMS Journal on Computing and Editor of the journal Artificial Intelligence.