Presenter: Britta Schulze, Bergische Universität Wuppertal

Title: Multi-Objective Unconstrained Combinatorial Optimization: A Polynomial Bound on the Number of Extreme Supported Solutions

Abstract: The multi-objective unconstrained combinatorial optimization problem (MUCO) can be interpreted as a specific relaxation of any multi-objective combinatorial optimization problem (MOCO) with linear sum objective function. While its single criteria analogon is analytically solvable, MUCO shares the computational complexity issues of most multi-objective combinatorial optimization problems: intractability and NP-hardness of the ?-constraint scalarizations.
We show that (1) the extreme supported points of a MUCO problem correspond to (2) the cells of an associated weight space decomposition, (3) the cells of an associated arrangement of hyperplanes, and (4) the nondominated extreme points of a corresponding zonotope. While the interrelation between (1) and (2) holds for general MOCO problems, (3) and (4) rely on the special structure of MUCO. Based on these interrelations, a polynomial bound on the number of extreme supported solutions can be derived, leading to an exact polynomial time algorithm to find all extreme supported solutions. As a side effect, nonextreme supported solutions can easily be identified in the arrangement of hyperplanes.  It is shown how this algorithm can be incorporated into a solution approach for multi-objective knapsack problems.

Organizer: Steen Nielsen

Host: Kim Allan Andersen