On October 13rd, 2022 Elina Rönnberg from Linköping University talked about Integer Programming Column Generation in order to accelerate branch-and-price for set covering, packing, and partitioning problems.

Abstract

Large-neighbourhood search (LNS) heuristics are important mathematical programming techniques that search for primal feasible solutions by solving an auxiliary problem with a restricted feasible region. Extending such powerful generic LNS heuristics to the branch-and-price context is inherently challenging. The most prominent challenges arise from the fact that in branch-and-price algorithms, columns are generated with the sole aim to solve linear programming relaxations. Hence, the ability to form integer feasible solutions is not considered during the generation of columns. Without any changes to the standard pricing schemes, the potential of deploying generic LNS heuristics within a branch-and-price procedure is severely limited.

We propose a matheuristic, based on an LNS heuristic framework, where the novelty is a customised pricing scheme for generating columns to solve an auxiliary problem. The theoretical foundation for this pricing scheme is a set of optimality conditions for integer programs. From this foundation, a column generation strategy is developed for finding columns that are likely to be of use in high-quality primal feasible solutions for the original problem. The proposed matheuristic is implemented in the generic branch-price-and-cut solver GCG. On a broad test set comprising classical block diagonal structured instances and general instances from the MIPLIB 2017 Collection, the computational results show a significant improvement to the solving performance of GCG.

About the Speaker

Elina Rönnberg is Senior Associate Professor in Optimisation and Deputy Head of the Department of Mathematics at Linköping University. Her research is in discrete optimisation, with a special interest in decomposition methods and applications within scheduling and resource allocation. The applied projects are often carried out in collaboration with industry or other stakeholders. Examples of applications are the design of electronic systems in aircraft and staff scheduling in healthcare. Contributions within decomposition methods include Dantzig-Wolfe decomposition, Lagrangian relaxation, column generation and logic-based Benders decomposition.