EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
2380. Generator sets for Minkowski Sums - Theory and Insights
Invited abstract in session MC-52: Multi-objective Combinatorial Optimization, stream Combinatorial Optimization.
Monday, 12:30-14:00Room: 8003 (building: 202)
Authors (first author is the speaker)
| 1. | Mark Lyngesen
|
| Department of Economics and Business Economics, Aarhus University | |
| 2. | Sune Lauth Gadegaard
|
| Department of Economics and Business Economics, Aarhus University | |
| 3. | Lars Relund Nielsen
|
| Economics, Aarhus University |
Abstract
In this presentation we consider a class of multi-objective optimization problems known as Minkowski sum problems or Pareto sum problems. Pareto sum problems are multi-objective optimization problems with a decomposable structure where the (global) Pareto set (the nondominated points of the feasible objective space) can be described as the Pareto set of the Minkowski sum of several (local) Pareto sets obtained from subproblems. Much research has been done on efficiently filtering for the set of (global) Pareto sum given several known (local) Pareto sets. In some cases, only subsets of the (local) Pareto sets are required for generating the global Pareto sum. As such, if a subproblem solution does not contribute in generating the (global) Pareto sum, then the computational effort spent on finding the solution is effectively wasted. For this reason, we investigate how small a subset of the Pareto optimal solutions from subproblems is necessary to describe the Pareto sum. Furthermore, we investigate when unnecessary Pareto optimal solutions exists in the subproblems and how to identify them. For this purpose we propose so-called generator upper bound sets, which can be used when solving the subproblems to exclude some unnecessary solutions. If and when these non-generating or unnecessary Pareto optimal solutions can be identified and excluded, the computational burden of identifying a generating subset of Pareto optimal solutions of a subset may be substantially reduced.
Keywords
- Multi-Objective Decision Making
- Programming, Multi-Objective
- Combinatorial Optimization
Status: accepted
Back to the list of papers