Pareto Leap: An Algorithm for Biobjective Mixed-Integer Programming

Many real-life optimization problems need to make decisions with discrete variables and multiple, conflicting objectives. Due to this need, the ability to solve such problems is an important and active area of research. We present a new algorithm, called Pareto Leap, for identifying the (weak) Pareto slices of biobjective mixed-integer programs (BOMIPs), even when Pareto slices intersect. The underlying theory holds for BOMIPs whose continuous relaxations are nonlinear, while the implementation of the algorithm is limited only by the capability of solvers that are used. The algorithm works by starting on a Pareto slice of the outcome set of a BOMIP and then “leaping” to another Pareto slice, which we demonstrate on numerical examples.

Article

Download

View PDF