Skip to main content
SpringerLink
Log in

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

  • Invited Review
  • Published:
EURO Journal on Decision Processes

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Notes

  1. Using the CSS, we will necessarily reach a point where we have \(mMR(\mathcal {X}, \Omega ) \le \delta\) for any threshold \(\delta \ge 0\). Indeed, at each iteration step, we can always choose \(x^*\) and \(y^*\) such that we have \(PMR(x^*,y^*,\Omega ) > 0\) and \(PMR(y^*,x^*,\Omega ) > 0\) before asking the query, and after collecting the DM’s answer, one of these values will become smaller or equal to zero. Then the result derives from the fact that the set \(\mathcal {X}\) of solutions is finite.

  2. The numerical tests were performed on an Intel Core i7-4770 CPU with 15GB de RAM.

References

  • Benabbou N, Perny P (2015a) Combining preference elicitation and search in multiobjective state-space graphs. In: Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25–31, 2015, pp 297–303

  • Benabbou N, Perny P (2015b) Incremental weight elicitation for multiobjective state space search. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25–30, 2015, Austin, Texas, USA, pp 1093–1099

  • Benabbou N, Perny P (2015c) On possibly optimal tradeoffs in multicriteria spanning tree problems. In: Algorithmic Decision Theory—4th International Conference, ADT 2015, Lexington, KY, USA, September 27–30, 2015, pp 322–337

  • Benabbou N, Perny P (2016) Solving multi-agent knapsack problems using incremental approval voting. ECAI 2016–22nd European Conference on Artificial Intelligence, 29 August–2 September 2016. The Netherlands, The Hague, pp 1318–1326

  • Benabbou N, Perny P (2017) Adaptive elicitation of preferences under uncertainty in sequential decision making problems. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19–25, 2017, pp 4566–4572

  • Benabbou N, Gonzales C, Perny P, Viappiani P (2015) Minimax regret approaches for preference elicitation with rank-dependent aggregators based on Choquet integral. EURO J Decis Process 3(1,2):29–64

    Article  Google Scholar 

  • Benabbou N, Diodoro SDSD, Perny P, Viappiani P (2016) Incremental preference elicitation in multi-attribute domains for choice and ranking with the borda count. In: Schockaert S, Senellart P (eds) Scalable uncertainty management. SUM 2016. Lecture Notes in Computer Science, vol 9858. Springer, Cham, pp 81–95

    Google Scholar 

  • Benabbou N, Perny P, Viappiani P (2017) Incremental elicitation of Choquet capacities for multicriteria choice, ranking and sorting problems. Artif Intell 246:152–180

    Article  Google Scholar 

  • Bourdache N, Perny P (2017) Anytime algorithms for adaptive robust optimization with OWA and WOWA. In: Rothe J (ed) 5th international conference on algorithmic decision theory (ADT 2017). Lecture Notes in Computer Science, vol 10576. Springer, Cham, pp 93–107

    Google Scholar 

  • Boutilier C, Brafman RI, Domshlak C, Hoos HH, Poole D (2004) Preference-based constrained optimization with CP-nets. Comput Intell 20(2):137–157

    Article  Google Scholar 

  • Boutilier C, Patrascu R, Poupart P, Schuurmans D (2006) Constraint-based optimization and utility elicitation using the Minimax decision criterion. Artif Intell 170(8–9):686–713

    Article  Google Scholar 

  • Brafman RI, Domshlak C (2009) Preference handling—an introductory tutorial. AI Mag 30(1):58–86

    Article  Google Scholar 

  • Braziunas D (2011) Decision-theoretic elicitation of generalized additive utilities. PhD thesis, University of Toronto

  • Braziunas D, Boutilier C (2007) Minimax regret-based elicitation of generalized additive utilities. In: Proceedings of the twenty-third conference on uncertainty in artificial intelligence (UAI-07). Vancouver, pp 25–32

  • Chajewska U, Koller D, Parr R (2000) Making rational decisions using adaptive utility elicitation. In: Proceedings of the seventeenth national conference on artificial intelligence (AAAI-00). Austin, pp 363–369

  • Dery LN, Kalech M, Rokach L, Shapira B (2014) Reaching a joint decision with minimal elicitation of voter preferences. Inf Sci 278:466–487

    Article  Google Scholar 

  • Domshlak C, Hüllermeier E, Kaci S, Prade H (2011) Preferences in AI: an overview. Artif Intell 175(7–8):1037–1052

    Article  Google Scholar 

  • Drummond J, Boutilier C (2014) Preference elicitation and interview minimization in stable matchings. In: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, July 27–31, 2014, Québec City, Québec, Canada, pp 645–653

  • Ehrgott M (2005) Multicriteria optimization, 2nd edn. Springer, New York

    Google Scholar 

  • Gelain M, Pini MS, Rossi F, Venable KB, Walsh T (2010) Elicitation strategies for soft constraint problems with missing preferences: Properties, algorithms and experimental studies. Artif Intell 174(3):270–294

    Article  Google Scholar 

  • Gilbert H, Spanjaard O, Viappiani P, Weng P (2015) Reducing the number of queries in interactive value iteration. In: Proceedings of ADT’15, pp 139–152

    Chapter  Google Scholar 

  • Gilbert H, Benabbou N, Perny P, Spanjaard O, Viappiani P (2017) Incremental decision making under risk with the weighted expected utility model. In: Proceedings of the twenty-sixth international joint conference on artificial intelligence, IJCAI 2017, Melbourne, Australia, August 19–25, 2017, pp 4588–4594

  • Ha V, Haddawy P (1997) Problem-focused incremental elicitation of multi-attribute utility models. In: Proceedings of the thirteenth conference on uncertainty in artificial intelligence, pp 215–222

  • Hamacher H, Ruhe G (1994) On spanning tree problems with multiple objectives. Ann Oper Res 52:209–230

    Article  Google Scholar 

  • Hansen P (1980) Bicriterion path problems. Multiple criteria decision making theory and application. Springer, Berlin Heidelberg, pp 109–127

    Chapter  Google Scholar 

  • Hart PE, Nilsson NJ, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Man Cybern 4(2):100–107

    Google Scholar 

  • Hines G, Larson K (2010) Preference elicitation for risky prospects. In: Proceedings of the 9th international conference on autonomous agents and multiagent systems. AAMAS ’10, vol 1. International Foundation for Autonomous Agents and Multiagent Systems, Toronto pp 889–896

    Google Scholar 

  • Kaddani S, Vanderpooten D, Vanpeperstraete JM, Aissi H (2017) Weighted sum model with partial preference information: application to multi-objective optimization. Eur J Oper Res 260:665–679

    Article  Google Scholar 

  • Koriche F, Zanuttini B (2010) Learning conditional preference networks. Artif Intell 174(11):685–703

    Article  Google Scholar 

  • Kouvelis P, Yu G (1997) Robust discrete optimization and its applications. Kluwer, Dordrechet

    Book  Google Scholar 

  • Kruskal JB (1956) On the shortest spanning subtree of a graph and the traveling salesman problem. Proc Am Math Soc 7:48–50

    Article  Google Scholar 

  • Kuhn HW (1955) The Hungarian method for the assignment problem. Naval Res Logist Quart 2:83–97

    Article  Google Scholar 

  • Lu T, Boutilier C (2011) Robust approximation and incremental elicitation in voting protocols. In: IJCAI 2011, Proceedings of the 22nd international joint conference on artificial intelligence, Barcelona, Catalonia, Spain, July 16–22, 2011, pp 287–293

  • Mandow L, De la Cruz JLP (2005) A new approach to multiobjective A* search. In: Proceedings of the XIX international joint conference on artificial intelligence (IJCAI 2005), pp 218–223

  • Perny P, Viappiani P, Boukhatem A (2016) Incremental preference elicitation for decision making under risk with the rank-dependent utility model. In: Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence, UAI 2016, June 25–29, 2016, New York City, NY, USA

  • Prim RC (1957) Shortest connection networks and some generalizations. Bell Syst Tech J 36:1389–1401

    Article  Google Scholar 

  • Regan K, Boutilier C (2009) Regret-based reward elicitation for Markov decision processes. In: Proceedings of the 25th conference on uncertainty in artificial intelligence (UAI 2009), Montreal, QC, Canada, pp 444–451

  • Salo A, Hämäläinen RP (2001) Preference ratios in multiattribute evaluation (PRIME)-elicitation and decision procedures under incomplete information. IEEE Trans Syst Man Cybernet 31(6):533–545

    Article  Google Scholar 

  • Savage LJ (1954) The foundations of statistics. Wiley, New York

    Google Scholar 

  • Stewart BS, White CC III (1991) Multiobjective A*. J ACM 38(4):775–814

    Article  Google Scholar 

  • Wang T, Boutilier C (2003) Incremental Utility Elicitation with the Minimax Regret Decision Criterion. In: Proceedings of the eighteenth international joint conference on artificial intelligence. pp 309–316

  • Weng P, Zanuttini B (2013) Interactive value iteration for markov decision processes with unknown rewards. In: International joint conference on artificial intelligence. pp 2415–2421

  • White CC III, Sage AP, Dozono S (1984) A model of multiattribute decisionmaking and trade-off weight determination under uncertainty. IEEE Trans Syst Man Cybern 14(2):223–229

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. NUS School of Computing, COM1, National University of Singapore, 13 Computing Drive, Singapore, 117417, Singapore

    Nawal Benabbou

  2. CNRS, Laboratoire d’informatique de Paris 6, LIP6, Sorbonne Université, 75005, Paris, France

    Patrice Perny

Authors
  1. Nawal Benabbou
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Patrice Perny
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Nawal Benabbou.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Benabbou, N., Perny, P. Interactive resolution of multiobjective combinatorial optimization problems by incremental elicitation of criteria weights. EURO J Decis Process 6, 283–319 (2018). https://doi.org/10.1007/s40070-018-0085-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s40070-018-0085-4

Keywords

Search

Navigation