EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
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:00Room: 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
- Programming, Integer
- Scheduling
Status: accepted
Back to the list of papers