The Cunningham-Geelen Method in Practice: Branch-Decompositions and Integer Programming

INFORMS Journal on Computing · 2013 · Volume 25 · Issue 4

Abstract

In 2007, W. H. Cunningham and J. Geelen describe an algorithm for solving m a x ⁡ { 𝑐 𝑇 ⁢ 𝑥 : 𝐴 ⁢ 𝑥 = 𝑏 , 𝑥 ≥ 0 , 𝑥 ∈ ℤ 𝑛 } max ⁡ { c T ⁢ x : A ⁢ x = b , x ≥ 0 , x ∈ ℤ n } , where 𝐴 ∈ ℤ 𝑚 × 𝑛 ≥ 0 A ∈ ℤ ≥ 0 m × n , 𝑏 ∈ ℤ 𝑚 b ∈ ℤ m , and 𝑐 ∈ ℤ 𝑛 c ∈ ℤ n , which utilizes a branch-decomposition of the matrix A and techniques from dynamic programming. In this paper, we report on the first implementation of the CG algorithm and compare our results with the commercial integer programming software Gurobi . Using branch-decomposition trees produced by heuristics and optimal trees produced by algorithms developed in our previous studies, we test both a memory-intensive and low-memory version of the CG algorithm on problem instances such as graph 3-coloring, set partition, market split, and knapsack. We isolate a class of set partition instances where the CG algorithm runs twice as fast as Gurobi , and demonstrate that certain infeasible market split and knapsack instances with width ≤6 range from running twice as fast as Gurobi , to running in a matter of minutes versus a matter of hours.

Keywords

optimization, integer programming, branch-decompositions

Enable JavaScript for citation tools and additional paper interactions.