EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
4173. On computing the Edgeworth–Pareto hull of multi-objective mixed-integer linear programming problems via an outer approximation algorithm
Invited abstract in session WD-37: Multiobjective Mixed-Integer Linear Optimization, stream Multiobjective Optimization.
Wednesday, 14:30-16:00Room: 33 (building: 306)
Authors (first author is the speaker)
| 1. | Markus Sinnl
|
| Institute of Business Analytics and Technology Transformation, Johannes Kepler University Linz | |
| 2. | Fritz Bökler
|
| Computer Science, Algorithm Engineering, TU Dortmund | |
| 3. | Sophie Parragh
|
| Institute of Production and Logistics Management, Johannes Kepler University Linz | |
| 4. | Fabien Tricoire
|
| Institute for Transport and Logistics Management, Vienna University of Economics and Business |
Abstract
In this talk, we present an outer approximation algorithm for computing the Edgeworth–Pareto hull of multi-objective mixed-integer linear programming problems (MOMILPs). It produces the extreme points (i.e., the vertices) as well as the facets of the Edgeworth–Pareto hull. The algorithm relies on a novel oracle that solves single-objective weighted-sum problems and we show that the required number of oracle calls is polynomial in the number of facets of the convex hull of the extreme supported non-dominated points in the case of MOMILPs. Moreover, for the special case of multi-objective linear programming problems, by generating the Edgeworth–Pareto hull the algorithm solves the problem to global optimality. A computational study on a set of benchmark instances from the literature is provided.
Keywords
- Programming, Multi-Objective
- Mathematical Programming
- Programming, Integer
Status: accepted
Back to the list of papers