1 présentation

• 
  09h00 - 10h00

  Column Elimination for Arc Flow Formulations

  • van Hoeve Willem-Jan, prés., Carnegie Mellon University

  We present column elimination, an iterative framework for solving integer programming problems expressed as arc-flow formulations. In these models, a feasible solution corresponds to a collection of paths through a directed acyclic graph, and the problem reduces to solving a constrained network flow. Because the graphs can quickly grow prohibitively large, column elimination begins with a smaller, relaxed representation of the graph, obtained from a relaxed dynamic program, that admits infeasible paths. At each iteration, we solve the relaxed network flow problem, identify and remove infeasible paths in the solution, and repeat until an optimal feasible solution is found. The term 'column elimination' stems from the fact that each path corresponds to a column in a Dantzig-Wolfe interpretation of the model. Perhaps surprisingly, this method can prove optimality using a relaxed network that can be orders of magnitude smaller than the exact network flow formulation. To accelerate the method, we utilize a dedicated subgradient algorithm to solve a Lagrangian relaxation of the problem, which offers additional opportunities for graph refinement. We experimentally demonstrate that column elimination can be competitive with or outperform state-of-the-art methods on several problem domains. Specifically, 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.