Column Elimination: Solving Discrete Optimization Problems Using Arc Flow Formulations


We propose an exact algorithm for solving a class of discrete optimization problems that can have their feasible regions represented by an arc flow formulation over the state-transition graph of a dynamic program. We give computational results for solving graph multicoloring problems and vehicle routing problems with time windows.