Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

W. Cunningham and J. Geelen describe an algorithm for solving $\max\{c^Tx : Ax = b, x \geq 0, x \in \mathbb{Z}^n\}$, where $A \in \mathbb{Z}_{\geq 0}^{m \times n}, b \in \mathbb{Z}^m$, and $c \in \mathbb{Z}^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 \textsc{CG} algorithm, and compare our results with the commercial integer programming software \textsc{Gurobi}. Using branch-decomposition trees produced by the heuristics developed by Hicks et al., and optimal trees produced by the algorithm designed by I.V. Hicks, we test both a memory-intensive and low-memory version of the \textsc{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 \textsc{CG} algorithm runs twice as fast as \textsc{Gurobi}, and demonstrate that certain infeasible market split and knapsacks instances with width $\leq 6$ range from running twice as fast as \textsc{Gurobi}, to running in a matter of minutes versus a matter of hours.