Poster, MIP Workshop, Lexington, Kentucky
We introduce subset-row inequalities into column elimination. These inequalities are notoriously challenging to implement in related branch-and-cut-and-price methods. We show how these inequalities can be implemented in column elimination in a weakened form that differs from the one used in branch-and-cut-and-price. We show computational results to demonstrate this difference.
Presentation, INFORMS Annual Meeting, Phoenix, Arizona
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.
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.
Talk, CPAIOR, Nice, France
We introduce a column elimination procedure for the capacitated vehicle routing problem. Our procedure maintains a decision diagram to represent a relaxation of the set of feasible routes, over which we define a constrained network flow. The optimal solution corresponds to a collection of paths in the decision diagram and yields a dual bound. The column elimination process iteratively removes infeasible paths from the diagram to strengthen the relaxation. The network flow model can be solved as a linear program with a conventional solver or via a Lagrangian relaxation. To solve the Lagrangian subproblem more efficiently, we implement a special successive shortest paths algorithm. We introduce several cutting planes to strengthen the dual bound, including a new type of clique cut that exploits the structure of the decision diagram. We experimentally compare the bounds from column elimination with those from column generation for capacitated vehicle routing problems.
Talk, INFORMS Annual Conference, Indiannapolis, IN
A method called Column Elimination was recently introduced to generate both lower bounds and optimal solutions for the graph coloring problem. Based on dynamic programming and decision diagrams, this exact method begins with a relaxed state space and refines this space at each iteration. Our work provides methodological and computational comparisons between Column Elimination and Column Generation; it uses the Capacitated Vehicle Routing Problem (CVRP) as a case study.
Talk, Constraint Programming Conference, Haifa, Israel
We present an exact algorithm for graph coloring and maximum clique problems based on SAT technology.
Talk, INFORMS Computing Society Conference, Tampa Bay, FL
A recent work by van Hoeve introduced a decision diagram based iterative refinement algorithm for finding multi-path solutions to optimization problems. We study the addition of branch and bound to this algorithm, including the well-known Zykov branching rule for graph coloring.
Talk, INFORMS Annual Conference, Anaheim, CA
A decision diagram approach was recently introduced to generate lower bounds for the graph coloring problem. It uses compilation via iterative refinement, which requires a variable ordering to be specified in advance. Oftentimes no single variable ordering dominates all others for a set of problem instances. This work provides an analysis and experimental evaluation of different variable ordering strategies including using portfolios of variable orderings.
Talk, CPAIOR, Virtual
Studying the use of portfolios of variable orderings on the performance of a decision diagram based algorithm for finding graph coloring lower bounds