Combining Preference Elicitation with Local Search and Greedy Search for Matroid Optimization

Authors

  • Nawal Benabbou Sorbonne Université, LIP6, Paris
  • Cassandre Leroy Sorbonne Université, LIP6, Paris
  • Thibaut Lust Sorbonne Université, LIP6, Paris
  • Patrice Perny Sorbonne Université, LIP6, Paris

DOI:

https://doi.org/10.1609/aaai.v35i14.17452

Keywords:

Other Foundations of Search & Optimization

Abstract

We propose two incremental preference elicitation methods for interactive preference-based optimization on weighted matroid structures. More precisely, for linear objective (utility) functions, we propose an interactive greedy algorithm interleaving preference queries with the incremental construction of an independent set to obtain an optimal or near-optimal base of a matroid. We also propose an interactive local search algorithm based on sequences of possibly improving exchanges for the same problem. For both algorithms, we provide performance guarantees on the quality of the returned solutions and the number of queries. Our algorithms are tested on the uniform, graphical and scheduling matroids to solve three different problems (committee election, spanning tree, and scheduling problems) and evaluated in terms of computation times, number of queries, and empirical error.

Downloads

Published

2021-05-18

How to Cite

Benabbou, N., Leroy, C., Lust, T., & Perny, P. (2021). Combining Preference Elicitation with Local Search and Greedy Search for Matroid Optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 35(14), 12233-12240. https://doi.org/10.1609/aaai.v35i14.17452

Issue

Section

AAAI Technical Track on Search and Optimization