Tractability in multi-objective combinatorial optimization

Tractability in multi-objective combinatorial optimization

Projektbeschreibung

Several results in the literature have shown that multi-objective combinatorial optimization (MOCO) problems are hard to be solved from a computational complexity point of view, which impairs the application of these concepts in real-life problems. However, recent results in the literature show that there exist several particular cases of these problems that can be solved in polynomial amount of time. Therefore, the identification of tractable particular cases of multi-objective combinatorial optimization problems is of interest both from a practical and theoretical point of view. The main research goals of this project are

  1. to characterize and recognize polynomial solvability of MOCO problems and

  2. to derive general methodologies to design efficient polynomial time algorithms for tractable cases.

 

Research Team

 

Workshops and Talks

Workshops

DAAD_Coimbra_1280x850.jpg
Workshop Participants, Coimbra, 14 to 19 September 2015<br /> Fachbereich 3: Mathematik / Naturwissenschaften / Aktuelles / Archiv / 2015 / Meldungen / Kooperation mit Portugal

 

Beschreibung

Participants of the joint DAAD Workshop in September 2016 at Universität Koblenz-Landau

 

  • Initial project meeting in Wuppertal (from 7 to 11 Septermber 2015)
  • Project meeting in Coimbra (from 14 to 19 September 2015)
  • Project meeting in Coimbra (from 29 November to 2nd December 2015)
  • Project meeting in Coimbra (from 29 February to 04 March 2016)
  • Workshop in Koblenz (from 05 September to 07 September 2016, joint workshop with the group of the MMDF project)
  • Project meeting in Coimbra (from 12 to 16 December 2016)

Talks

  • Ruzika, S.: A General Approximation Method for Bicriteria Minimization Problems, INFORMS Annual Meeting, Nashville, TN, USA, 13.11.-16.11.2016
  • Ruzika, S.: A General Bicriteria Approximation Algorithm, Gastvortrag an der Universität Göttingen, 26.01.2017
  • Willems, D.: A Sandwich Approximation Algorithm for Biobjective Optimal Control Problems, Kickoff Workshop „Multi-objective Combinatorial Optimization: Beyond the Biobjective Case“, Wuppertal
  • Klamroth, K.: A Multiple Objective View on Robust Optimization and Stochastic Programming. Invited talk, Workshop "Women in Optimization", Heidelberg, 02.-04.03.2015
  • Ruzika, S.: Why would you ever „vectorize“ a single objective optimization problem?, Keynote-Vortrag bei Recent Advances in Multi-Objective Optimization, Nantes
  • Torchiani, C.: Single- and biobjective timetabling for shuttle buses, 27th European Conference on Operational Research (EURO) 2015
  • Ohst, J.: A qualitative formula for evacuation times, based on a case study of a nuclear power plant evacuation, 27th European Conference on Operational Research (EURO) 2015
  • Ruzika, S.: Toward a Methodology of Combining Optimization Models, 27th European Conference on Operational Research (EURO) 2015
  • Torchiani, C.: Shortest Path with shortest detours, 23rd International Conference on Multiple Criteria Decision Making (MCDM) 2015, Hamburg
  • Klamroth, K: A Multiple Objective View on Outlier Handling at the Example of Center Location Problems, 23rd International Conference on Multiple Criteria Decision Making (MCDM) 2015, Hamburg
  • Ruzika, S.: A coverage-based Box-Algorithm to compute a representation for optimization problems with three objective functions, 23rd International Conference on Multiple Criteria Decision Making (MCDM) 2015, Hamburg
  • Schulze, B.: Multiple objective optimization for multidimensional knapsack problems, 23rd International Conference on Multiple Criteria Decision Making (MCDM) 2015, Hamburg
  • Stiglmayr, M.: Bicriteria Fixed-Charge Network Flow - Separating Fixed Costs and Flow Costs, 23rd International Conference on Multiple Criteria Decision Making (MCDM) 2015, Hamburg
  • Ruzika, S.: A biobjective routing problem with application to emergency planning, Jahrestagung der GOR 2015, Wien
  • Willems, D.: Bicriteria Optimal Control, Jahrestagung der GOR 2015, Wien
  • Klamroth, K.: Multiple Objective Optimization: Trading Off between Objectives, Constraints and Robustness Criteria. Plenary talk at IFIP 2015

 

 

The project is funded by DAAD - "Deutscher Akademischer Austausch Dienst", Project-ID 57128839, and FCT - "Fundação para a Ciência e Tecnologia".

Projektinformationen

Projektpartner
  • Universität Koblenz-Landau, Campus Koblenz
  • Bergische Universität Wuppertal
  • Universidade de Coimbra
Finanzierung: DAAD & FCT
Zeitraum: 01.01.2015 bis 31.12.2016

Mitarbeiter


Literatur

Veröffentlichungen

2016

Willems2016ASA
Willems, David; Wijaya, Karunia Putra; Ruzika, Stefan; Götz, Thomas (2016): A Sandwich Approximation Algorithm for Biobjective Optimal Control Problems.

2015

Fonseca2015OTQ
Fonseca, Carlos; Paquete, Luís; Ruzika, Stefan; Schulze, Britta; Stiglmayr, Michael; Willems, David (2015): On the Quadratic Knapsack Problem.

Halffmann2015ETS
Halffmann, Pascal; Willems, David; Ruzika, Stefan; José Rui, Figueira; Klamroth, Kathrin; Schulze, Britta; Paquete, Luís; Stiglmayr, Michael; Fonseca, Carlos (2015): Easy to say they’re hard, but hard to see they’re easy – Toward a categorization of tractable multiobjective combinatorial optimization problems. In: Journal of Multi-Criteria Decision Analysis.

Halffmann2015AGA1
Halffmann, Pascal; Willems, David; Ruzika, Stefan; Thielen, Clemens (2015): A General Approximation Method for Bicriteria Minimization Problems.

2014

Torchiani2014SPW
Torchiani, Carolin; Ohst, Jan; Willems, David; Ruzika, Stefan (2014): Shortest paths with shortest detours: A bi-objective routing problem.

kein Jahr angegeben

SchulzeyearDSR
Schulze, Britta; Stiglmayr, Michael; Paquete, Luís; Klamroth, Kathrin; Figueira, José: Decision Space Robustness.

SchulzeyearCOS
Schulze, Britta; Klamroth, Kathrin; Stiglmayr, Michael: Computation of Supported Solutions for Binary Multiple Objective Programming Problems.

SchulzeyearSAF
Schulze, Britta; Paquete, Luís; Klamroth, Kathrin; Figueira, José: Sensitivity analysis for bi-dimensional (0,1)-knapsack problems: a bi-objective approach.