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

Nawal Benabbou () and Patrice Perny ()
Additional contact information
Nawal Benabbou: National University of Singapore
Patrice Perny: Sorbonne Université

EURO Journal on Decision Processes, 2018, vol. 6, issue 3, No 4, 283-319

Abstract: Abstract We propose an introduction to the use of incremental preference elicitation 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 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.

Keywords: Multiobjective combinatorial optimization; Preference elicitation; Imprecise weights; Minimax regret (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s40070-018-0085-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:eurjdp:v:6:y:2018:i:3:d:10.1007_s40070-018-0085-4

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/40070

DOI: 10.1007/s40070-018-0085-4

Access Statistics for this article

EURO Journal on Decision Processes is currently edited by Vincent Mousseau

More articles in EURO Journal on Decision Processes from Springer, EURO - The Association of European Operational Research Societies
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().