EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3102. Local Branching techniques to strengthen Logic-Based Benders Decomposition

Invited abstract in session WA-25: Topics in Integer Programming I, stream Combinatorial Optimization.

Wednesday, 8:30-10:00
Room: 011 (building: 208)

Authors (first author is the speaker)

1. Ioannis Avgerinos
Department of Management Science and Technology, Athens University of Economics and Business
2. Yiannis Mourtos
Management Science & Technology, Athens University of Economics & Business
3. Stavros Vatikiotis
Department of Management Science and Technology, Athens University of Economics and Business
4. Georgios Zois
Management Science and Technology, Athens University of Economics and Business

Abstract

This work focuses on the integration of Local Branching into Logic-Based Benders Decomposition (LBBD) schemes. Given a MILP formulation for scheduling on unrelated parallel machines, it is noticed that certain k-OPT neighbourhoods could implicitly be explored by regular local search operators. After enumerating such neighbourhoods and obtaining their local optima, a local branching cut (applied as a Benders cut) eliminates all their solutions at once, thus avoiding an overload of the master problem with thousands of Benders cuts. To guarantee convergence to optimality, the constructed neighbourhood should be exhaustively explored - this procedure is accelerated by domination rules or selectively implemented on nodes which are more likely to reduce the optimality gap.
In this study, we implement internal swaps of jobs, i.e. swaps between jobs on the same machine, over the solution of the master problem, to construct formulation-specific 4-OPT neighbourhoods. The experimentation on two challenging scheduling problems (i.e., the minimisation of total completion times and the minimisation of total tardiness on unrelated machines with sequence-dependent and resource-constrained setups) shows considerable reduction of optimality gaps or acceleration of convergence, in comparison with regular Benders cuts. As our approach is easily transferrable to different optimisation problems, it provides a promising prospect to improve the performance of regular LBBD algorithms.

Keywords

Status: accepted


Back to the list of papers