Addressing redundancy in column generation using Benders' decomposition cuts

Speaker: 

Dr Stephen J Maher

Affiliation: 

Zuse Institute Berlin / Lancaster University

Date: 

Thu, 16/05/2019 - 11:05am

Venue: 

MC-032, The Red Centre, UNSW

Abstract: 

When solving the linear programming (LP) relaxation of a mixed-integer program (MIP) with column generation, columns might be generated that are not needed to express any integer optimal solution of the MIP. Such columns are called strongly redundant and the dual bound obtained by solving the LP relaxation is potentially stronger if these columns are not generated. We introduce a sufficient condition for strong redundancy that can be checked by solving a compact LP. Using a dual solution of this compact LP we generate classical Benders cuts for the subproblem so that the generation of strongly redundant columns can be avoided. The potential of these cuts to improve the dual bound of the column generation master problem is evaluated computationally using an implementation in the branch-price-and-cut solver GCG. While their efficacy is limited on classical problems, the cuts’ usefulness is significantly demonstrated on structured models, when a temporal decomposition can be applied.

Dr Stephen J Maher is an alumnus of UNSW, having completed his PhD in Mathematics in 2014. Since completing his PhD, Stephen has work in research groups at the Zuse Institute Berlin and Lancaster University. Stephen is a core member of the development team for the mixed integer programming solver SCIP, which is hosted at the Zuse Institute Berlin. As part of this role, he has investigate the use of decomposition techniques in various parts of mixed integer programming solvers. Most recently, his work has involved the development of a general framework for the classical mathematical programming technique of Benders' Decomposition. Stephen has also started an initiative to educate people about optimisation in the real world through his website www.optimisationintherealworld.co.uk.

 

 

 

 

School Seminar Series: