06.06.2011

Informatik-Kolloquium

Im Sommersemester 2011 findet im Rahmen des Informatik-Kolloquiums der folgende Vortrag statt:

Montag, 6. Juni 2011, 17:00 Uhr, Turing-Hörsaal

 

Prof. Dr. Kathrin Klamroth  (Bergische Universität Wuppertal)

Multi-Criteria Combinatorial Optimization

In practical applications of Operations Research it is frequentlyobserved that the decision maker prefers apparently suboptimalsolutions. A natural explanation for this phenomenon is that theapplied mathematical model did not fully represent all thedecision makers criteria and constraints. Multiple objectiveoptimization approaches are specifically designed to incorporatesuch complex preference structures, and they gain more and moreimportance in various application areas like engineering designand supply chain management.

After discussing the pros and cons of multiple objective modelsin general, we focus on multiple objective combinatorialoptimization (MOCO) problems. Typical examples of MOCO problemsinclude multiple objective knapsack problems, multiple objectiveassignment problems, the multiple objective traveling salesmanproblem, and other network problems like multiple objectiveminimum spanning tree, shortest path, and minimum cost flowproblems.

Structural properties of the efficient set of MOCO problems playa crucial role for the development of efficient solutionmethods. A central question relates to the connectedness of theefficient set with respect to combinatorially or topologicallymotivated neighborhood structures. A positive answer to thisquestion would provide a theoretical justification for theapplication of fast neighborhood search techniques, not only formultiple objective but also for appropriate formulations ofsingle objective problems. We will address this question bothwith theoretical and with numerical arguments.