Title:

Incorporating Dantzig-Wolfe Decomposition Into Branch-and-Cut by Cutting Planes

Abstract:

Dantzig-Wolfe (DW) decomposition is a well-known technique in mixed integer programming (MIP) for decomposing and convexifying constraints to obtain potentially strong dual bounds. We investigate Fenchel cuts that can be derived using the DW decomposition algorithm and show that these cuts can provide the same dual bounds as DW decomposition. We show that these cuts, in essence, decompose the objective function cut one can simply write using the DW bound. Compared to the objective function cut, these Fenchel cuts lead to a formulation with lower dual degeneracy, and consequently a better computational performance under the standard branch-and-cut framework in the original space. We also discuss how to strengthen these cuts to improve the computational performance further. We test our approach on the Multiple Knapsack Assignment Problem and show that the proposed cuts are helpful in accelerating the solution time without the need to implement branch-and-price. 

Bio: 

Oktay Günlük is a professor of practice at Cornell University, School of ORIE. Before joining Cornell, he was the manager of the Mathematical Optimization and Algorithms group at IBM Research. He has also spent three years as a researcher in the Operations Research group in AT&T Labs. At both of these industrial labs, in addition to basic research in mathematical optimization, he has worked on various large-scale applied optimization projects for internal and external customers.

Oktay Günlük's main research interests are related to theoretical and computational aspects of discrete optimization problems, mainly in the area of integer programming. In particular, his main body of work is in the area of cutting planes for mixed-integer sets. Some of his recent work focuses on developing integer programming based approaches to machine learning problems.