Skip to main content

Elina Rönnberg: Integer programming column generation

Integer programming column generation: Accelerating branch-and-price using a novel pricing scheme for finding high-quality solutions in set covering, packing, and partitioning problems

Time: Fri 2021-12-10 11.00 - 12.00

Location: Seminar room 3721

Video link: Zoom 63658381373

Language: English

Lecturer: Elina Rönnberg


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 extremely challenging.
The most prominent challenges arises 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.
 
This paper proposes 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.
 
 

Page responsible:Per Enqvist
Belongs to: Department of Mathematics
Last changed: Dec 06, 2021