TA8 - Primal Integer Programming

Exact methods such as Branch & Cut, Branch & Price, and Lagrangian decomposition perform well on many MIP problems up to moderate size. However, at larger scales, these dual-fractional approaches struggle to quickly produce high-quality integer solutions, unlike primal heuristics. This talk explores how to “primalize” such exact methods.

In this talk, I will present a hybrid framework that integrates GISUD, a newly exact primal integer programming approach, into a column generation scheme to solve large-scale generalized set partitioning problems with integer right-hand sides. Primal methods are the ones that, starting from a feasible solution, find an improving sequence such that, with strict improvement, we reach an optimality while preserving feasibility.
We evaluate our method on the Airline Crew Rostering Problem, demonstrating its efficacy in solving real-world industrial problems.

In this talk, we revisit primalization, a class of approaches that aim to exploit primal information more effectively to obtain high-quality solutions to large-scale optimization problems. We use Benders decomposition as our discussion framework, a widely used technique for problems with complicating variables that, when fixed, yield much easier subproblems. In its classical form, however, Benders decomposition does not leverage primal information and repeatedly solves highly similar subproblems, often exhibiting zigzagging behavior across iterations and leading to slow convergence, particularly in large-scale settings. We discuss the main principles underlying primalization and highlight their implications for computational performance. Building on these insights, we outline promising extensions within the Benders framework, including the use of optimization proxies. Finally, we present computational results on facility location problems.

The generalized set partitioning problem is a set partitioning problem in which one or more right-hand sides exceed one. This arises in situations where certain tasks must be covered multiple times or by several crew members. In this case, we lose quasi-integrality, which is necessary for applying integral simplex-like methods. In this talk, we present ideas to recover quasi-integrality and report results on real aircrew scheduling problems.