EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3865. Lagrangean lower bounding and math-heuristics for approximating the set of non-dominated points of a computationally demanding bi-objective MILP

Invited abstract in session WD-37: Multiobjective Mixed-Integer Linear Optimization, stream Multiobjective Optimization.

Wednesday, 14:30-16:00
Room: 33 (building: 306)

Authors (first author is the speaker)

1. Ann-Brith Strömberg
Mathematical Sciences, Chalmers University of Technology
2. Gabrijela Obradovic
Chalmers University of Technology
3. Felix Held
Chalmers University of Technology
4. Kristian Lundberg
Saab AB

Abstract

We consider a computationally demanding bi-objective MILP, arising from an industrial maintenance and workshop scheduling problem subject to a turn–around time contract. Since, for industrial scale instances, this problem cannot be solved in reasonable computing time, we employ (i) so-called job variables in the workshop model, and (ii) a lower bounding procedure based on Lagrangean relaxation of the complicating constraints of an epsilon-constraint scalarized problem combined with math-heuristics to identify approximately non-dominated feasible points. A Lagrangean dual of the scalarized problem is maximized using subgradient optimization, which is shown to provide lower bounding functions of the objective of the scalarazed problem over the domain of the epsilon-constrained objective. As a means to reduce computational complexity we introduce so-called job variables, however resulting in an in-definiteness of the Lagrangean dual variables. This is remedied by aggregating, over jobs, the constraints defining the objective, which in turn entails a relaxation of the scalarized problems in terms of lower optimal values. To mimic the turn–around time contract, the aggregated variables’ values are split into values for the original job variables. The lower bounds computed are, however, still valid, albeit slightly weaker as compared to when constraint aggregation is not employed. A topic for further research is tightening of these lower bounds.

Keywords

Status: accepted

Back to the list of papers