TY - JOUR

T1 - Equidistant representations: Connecting coverage and uniformity in discrete biobjective optimization

AU - Kidd, Martin Philip

AU - Lusby, Richard

AU - Larsen, Jesper

PY - 2020

Y1 - 2020

N2 - The nondominated frontier of a multiobjective optimization problem can be overwhelming to a decision maker, as it is often either very large or infinite in size. Instead, a discrete representation of this set in the form of a small sample of points is often preferred. In this paper we consider the Discrete Representation Problem (DRP), which is itself a triobjective optimization problem. The three objectives comprise three standard quality measures for discrete representations, namely coverage, uniformity and the cardinality of the set. We introduce the notion of complete equidistant representations, and prove that such a representation provides a nondominated solution to the DRP. In addition, we show through the help of complete equidistant representations that coverage and uniformity can be seen as dual problems given a fixed cardinality, and therefore that optimality gaps for coverage and uniformity can be obtained given any representation. Moreover, even though the definition of the coverage error requires the full nondominated set, we show how the coverage error for a given representation can be calculated by generating a much smaller set. Finally, we present a new method for finding discrete representations of a desired cardinality that outperforms existing methods w.r.t. coverage and uniformity on a set of mixed-integer programming benchmark instances.

AB - The nondominated frontier of a multiobjective optimization problem can be overwhelming to a decision maker, as it is often either very large or infinite in size. Instead, a discrete representation of this set in the form of a small sample of points is often preferred. In this paper we consider the Discrete Representation Problem (DRP), which is itself a triobjective optimization problem. The three objectives comprise three standard quality measures for discrete representations, namely coverage, uniformity and the cardinality of the set. We introduce the notion of complete equidistant representations, and prove that such a representation provides a nondominated solution to the DRP. In addition, we show through the help of complete equidistant representations that coverage and uniformity can be seen as dual problems given a fixed cardinality, and therefore that optimality gaps for coverage and uniformity can be obtained given any representation. Moreover, even though the definition of the coverage error requires the full nondominated set, we show how the coverage error for a given representation can be calculated by generating a much smaller set. Finally, we present a new method for finding discrete representations of a desired cardinality that outperforms existing methods w.r.t. coverage and uniformity on a set of mixed-integer programming benchmark instances.

KW - Biobjective optimization

KW - Discrete optimization

KW - Discrete representations

U2 - 10.1016/j.cor.2019.104872

DO - 10.1016/j.cor.2019.104872

M3 - Journal article

AN - SCOPUS:85078081478

VL - 117

JO - Computers & Operations Research

JF - Computers & Operations Research

SN - 0305-0548

M1 - 104872

ER -