Representative Solutions for Bi-Objective Optimisation

Authors

  • Emir Demirovi? University of Melbourne
  • Nicolas Schwind National Institute of Advanced Industrial Science and Technology

DOI:

https://doi.org/10.1609/aaai.v34i02.5501

Abstract

Bi-objective optimisation aims to optimise two generally competing objective functions. Typically, it consists in computing the set of nondominated solutions, called the Pareto front. This raises two issues: 1) time complexity, as the Pareto front in general can be infinite for continuous problems and exponentially large for discrete problems, and 2) lack of decisiveness. This paper focusses on the computation of a small, “relevant” subset of the Pareto front called the representative set, which provides meaningful trade-offs between the two objectives. We introduce a procedure which, given a pre-computed Pareto front, computes a representative set in polynomial time, and then we show how to adapt it to the case where the Pareto front is not provided. This has three important consequences for computing the representative set: 1) does not require the whole Pareto front to be provided explicitly, 2) can be done in polynomial time for bi-objective mixed-integer linear programs, and 3) only requires a polynomial number of solver calls for bi-objective problems, as opposed to the case where a higher number of objectives is involved. We implement our algorithm and empirically illustrate the efficiency on two families of benchmarks.

Downloads

Published

2020-04-03

How to Cite

Demirovi?, E., & Schwind, N. (2020). Representative Solutions for Bi-Objective Optimisation. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02), 1436-1443. https://doi.org/10.1609/aaai.v34i02.5501

Issue

Section

AAAI Technical Track: Constraint Satisfaction and Optimization