From Decision Theory to combinatorial optimization: 
problems and algorithms in graphs


Patrice Perny (LIP6, University of Paris 6)


The recent developments of Decision Theory have provided various
sophisticated preference models for decision making (DM) in complex
environments (DM under uncertainty and risk, Mutlicriteria DM and
collective DM). In this area, much effort is spent on the axiomatic
analysis of models, providing theoretical justifications for
descriptive and normative points of view. However, when the set of
alternatives has a combinatorial structure, the size of the search
space requires significant additional efforts to determine the
most-preferred solutions with respect to a given preference model.
Moreover, simple constructive approaches used in classical
combinatorial optimization (e.g. dynamic programming, greedy search)
do not automatically extend to cope with non-classical preferences
models (e.g. partial order on solutions, non-linear cost functions).
Hence, designing new search algorithms to determine the
most-preferred solutions becomes a critical issue.


Using classical graphs problems as illustrative examples (e.g.
shortest paths, minimal spanning trees), the aim of this
presentation is 1) to introduce preference-based search problems in
graphs in various contexts such as multiobjective optimization,
robust optimization and fair decision making, 2) to discuss
complexity issues and to suggest some preliminary solution
algorithms.