Tractability in multiobjective combinatorial optimization
Description
The main research goal of this project is to characterize and recognize polynomial solvability of multiobjetive combinatorial optimization problems. The project aims at exploring particular cases in order to understand the role of the problem structure, objectives and constraints in the tractability of these problems. Based on these findings, we plan to develop general methodologies to design efficient polynomial time algorithms for those particular cases. Of particular interest is to develop solution methods that find a representative subset of the Pareto optimal set, maximizing a given representation quality.
Researchers
Funded by
FCT/DAAD
Partners
University of Lisboa (IST), University of Wuppertal, University of Koblenz-Landau
Total budget
10 000,00 €
Local budget
3 500,00 €
Keywords
Multiobjective optiimization,algorithms
Start Date
2015-02-01
End Date
2017-01-31
Journal Articles
2017
(2 publications) - Lacour, R. and Klamroth, K. and Fonseca, C.M. , "A Box Decomposition Algorithm to Compute the Hypervolume Indicator", Computers & Operations Research, vol. 79, pp. 347-360, 2017
- Schulze, B. and Paquete, L. and Klamroth, K. and Figueira, J. , "Bi-dimensional knapsack problems with one soft constraint", Computers & Operations Research, vol. 78, pp. 15-26, 2017
Tech Report
2015
(1 publication) - Figueira, J. and Fonseca, C.M. and Halffmann, P. and Klamroth, K. and Paquete, L. and Ruzika, S. and Schulze, B. and Stiglmayr, M. and Willems, D. , "Easy to say they’re hard, but hard to see they’re easy: Toward a categorization of tractable multiobjective combinatorial optimization problems", 2015