We present column elimination as a general framework for solving (large-scale) integer programming problems. In this framework, solutions are represented compactly as paths in a directed acyclic graph. Column elimination starts with a relaxed representation, that may contain infeasible paths, and solves a constrained network flow over the graph to find a solution. It then iteratively refines the graph by eliminating infeasible paths until an optimal feasible solution is found. We introduce the notion of relaxed dynamic programs to generalize and formalize prior works that were developed for specific applications. We also present a subgradient method for solving the Lagrangian relaxation of the problem which provides additional graph refinement opportunities. Lastly, we propose extensions to include cut generation and branch-and-bound. Our experimental evaluation shows that column elimination can be competitive with or outperform state-of-the-art methods on various problem domains. Specifically, we find that column elimination closes five open instances of the graph multicoloring problem, one open instance with 1,000 locations of the vehicle routing problem with time windows, and six open instances of the pickup-and-delivery problem with time windows.
Citation
Submitted