Multi-Objective Mixed Integer Programming: An Objective Space Algorithm

Abstract

This paper introduces the first objective space algorithm which can exactly find all supported and non-supported non-dominated solutions to a mixed-integer multi-objective linear program with an arbitrary number of objective functions. This algorithm is presented in three phases. First it builds up a super-set which contains the Pareto front. This super-set is then modified to not contain any intersecting polytopes. Once this is achieved, the algorithm efficiently calculates which portions of the super-set are not part of the Pareto front and removes them, leaving exactly the Pareto front.

arXiv comment6 pages, presented at LeGO International Global Optimization Workshop. At time of submission, no competing algorithm was known, but a competing algorithm was published between submission and presentation of this work

References in corpus (2)

• Multi-objective integer programming: An improved recursive algorithm
• The vector linear program solver Bensolve -- notes on theoretical background