Interactive resolution of multiobjective combinatorial optimization problems by incremental elicitation of criteria weights - Sorbonne Université Access content directly
Journal Articles EURO journal on decision processes Year : 2018

Interactive resolution of multiobjective combinatorial optimization problems by incremental elicitation of criteria weights

Nawal Benabbou
Patrice Perny

Abstract

We propose an introduction to the use of incremental preference elicita-tion methods in the field of multiobjective combinatorial optimization. We consider three different optimization problems in vector-valued graphs, namely the shortest path problem, the minimum spanning tree problem and the assignment problem. In each case, the preferences of the decision maker over cost vectors are assumed to be representable by a weighted sum but the weights of criteria are initially unknown. We then explain how to interweave preference elicitation and search in order to quickly determine a near-optimal solution with a limited number of preference queries. This leads us to successively introduce an interactive version of dynamic programming, greedy search, and branch and bound to solve the problems under consideration. We then present numerical tests showing the practical efficiency of these algorithms that achieve a good compromise between the number of queries asked and the solution times.
Fichier principal
Vignette du fichier
nbppEJDPv9.pdf (396.92 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

hal-01796570 , version 1 (21-05-2018)

Identifiers

Cite

Nawal Benabbou, Patrice Perny. Interactive resolution of multiobjective combinatorial optimization problems by incremental elicitation of criteria weights. EURO journal on decision processes, In press, ⟨10.1007/s40070-018-0085-4⟩. ⟨hal-01796570⟩
164 View
277 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More