Lagrangian Bounding and Heuristics for Bi-Objective Discrete Optimisation

Abstract: For larger instances of multi-objective optimisation problems, the exact Pareto frontier can be both difficult and time-consuming to calculate. There is a wide range of methods to find feasible solutions to such problems, but techniques for finding good optimistic bounds to compare the feasible solutions with are missing. In this study, we investigate the use of Lagrangian relaxation to create optimistic bounds to bi-objective optimisation problems with complicating side constraints. The aim is to develop an effective method to produce optimistic bounds that are closer to the Pareto frontier than the commonly used linear programming bounds.  In order to use Lagrangian relaxation on the bi-objective problem, the objectives are combined using the weighted sum method. A Lagrangian dual function is then constructed by relaxing the complicating constraints and the subgradient method is used to optimise the dual problem in order to find an optimistic solution. By solving the single-objective problem for multiple weights, an optimistic bound to the Pareto frontier can be constructed. The subgradient method also includes a heuristic to find feasible solutions. The feasible solutions found by the heuristic form a pessimistic bound to the frontier. The method has been implemented and tested on several instances of a capacitated facility location problem with cost and CO2 emission as objectives. The results indicate that, by using Lagrangian relaxation, an optimistic bound close to the Pareto frontier can be found in a relatively short time. The heuristic used also manages to produce good pessimistic bounds, and hence the Pareto frontier can be tightly enclosed. The optimistic bounds found by Lagrangian relaxation are better and more consistent along the Pareto frontier than the bounds found by linear programming.