Combinatorial optimization problems with risk functions, budget type constraints and controllable data

Session : LTSS2 / LTSS2 : Problèmes de transport avec gestion des risques
Vendredi 12 février 15:00 - 15:40 Salle : GI042
Evgeny Gurevsky, Sergey Kovalev et Mikhail Kovalyov

The principal object of this study is a combinatorial problem of risk minimization with budget/knapsack type constraint and controllable data. This problem was introduced and proven to be polynomially solvable in Chen et al. (2009), where the authors describe, inter alia, its potential applications in the domain of routing and network design. Our main contribution deals with extending and improving the results obtained in Chen et al. (2009). Namely, at first we show that the studied problem is also polynomially solvable for a new class of risk functions that is larger than that presented in Chen et al. (2009) and suggest a faster original approach for its resolution. Secondly, we also consider a reverse version of the studied problem, introduced in {A}lvarez-Miranda et al. (2011), for which the roles of the objective function and the constraint are switched. To solve this problem, we develop a polynomial time algorithm, which outperforms the algorithm presented in {A}lvarez-Miranda et al. (2011). Finally, we show how to find a set of efficient (Pareto optimal) solutions of a bi-criteria version of the studied problem, where the knapsack type constraint becomes the second objective function to be minimized.

Mots clés : combinatorial optimization, knapsack constraints, shortest path, risk minimization, spanning tree, dynamic programming, bi-criteria problems, box constraints, controllable data