Ann-Brith Strömberg - Approximating the set of non-dominated points of a bi-objective MILP by means of Lagrangean lower bounding and math-heuristics

Abstract:
We consider a computationally demanding bi-objective mixed-integer linear optimization problem (BOMILP) arising from the simultaneous scheduling of maintenance of components of systems and scheduling of jobs in the maintenance workshop, subject to turn–around time limits for the maintained components. The objectives to minimize are (i) the cost of preventive maintenance and (ii) the risk of exceeding the contracted turn–around times. For industrial scale instances this BOMILP cannot be solved in reasonable computing time. To estimate the quality of a set of approximately non-dominated feasible points identified using math-heuristics, we develop a lower bounding procedure based on a Lagrangean relaxation of the complicating constraints of epsilon-constraint scalarized problems (MILPs).

The Lagrangean dual problem is solved using subgradient optimization, which is shown to provide lower bounding functions of the optimal values of the scalarized problems over the domain of the epsilon-constrained objective. To reduce the computational complexity of the MILPs we introduce so-called job variables, however resulting in an indefiniteness of the Lagrangean dual variables. This indefiniteness is remedied by aggregating—over jobs in the workshop—the constraints defining the objective, which in turn corresponds to an enlargement of the feasible sets of the epsilon-constraint MILPs, implying possibly lower optimal values. The lower bounds computed are, however, still valid. A topic for further research is tightening of these lower bounds