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

Nawal Benabbou, Cassandre Leroy, Thibaut Lust, Patrice PernyAAAI 2021 · DOI

Abstract

Combinatorial optimization often assumes precise knowledge of utility functions, which is rarely available in real-world decision support. This paper explores interactive algorithms for matroid optimization that interleave preference elicitation with search. By utilizing Minimax Regret (MMR) to guide queries, the proposed Interactive Greedy and Interactive Local Search algorithms find optimal or near-optimal solutions with minimal user effort. Experimental results across various matroid structures demonstrate that Local Search typically requires fewer queries, while the Greedy approach offers computational speed advantages.

1. Introduction

In many decision-making scenarios, the objective function is not fully known. For instance, in network design or committee selection, the "weights" assigned to individual elements are often subjective and reside within the mind of a human Decision Maker (DM). Traditional optimization requires these weights as input, but eliciting a full numerical utility function is cognitively demanding and prone to error. This paper addresses the challenge of preference elicitation in the context of matroids—mathematical structures that generalize the notion of linear independence and allow for efficient global optimization via simple algorithms like greedy search.

2. Problem Statement: Matroid Optimization under Uncertainty

A matroid is defined by a ground set of elements and a collection of independent sets. The goal is to find a "base" (a maximal independent set) that maximizes a linear utility function. When weights are unknown, we represent the DM's preferences as a set of possible weight functions $\Lambda$. The uncertainty in $\Lambda$ leads to potential "regret"—the difference between the utility of the chosen solution and the utility of the true optimal solution under the worst-case weight vector in $\Lambda$.

3. Preference Elicitation via Minimax Regret

The core strategy for reducing uncertainty is the Minimax Regret (MMR) criterion. MMR identifies the solution that minimizes the maximum possible loss. By asking the DM to compare two elements ("Which do you prefer, $e_1$ or $e_2$?"), the algorithm adds constraints to $\Lambda$, effectively shrinking the space of possible utility functions.

Evolution of the uncertainty set $\Lambda$ over successive queries, showing how the space of possible weight functions narrows.

As shown in the figure above, each query provides a linear constraint that cuts the feasible region of weight vectors, eventually narrowing down the space until a single optimal solution (or one within a tolerance $\delta$) can be identified.

4. Proposed Algorithms

The authors introduce two primary interactive frameworks based on classic optimization techniques:

  • Interactive Greedy Algorithm: This adapts the standard greedy approach. At each step, the algorithm attempts to pick the best available element. If the current uncertainty in $\Lambda$ makes it impossible to determine which element is superior according to the MMR criterion, a query is posed to the DM.
  • Interactive Local Search: This algorithm starts with an arbitrary base and explores its neighborhood by considering swaps (replacing one element in the base with one outside). A swap is performed if it is guaranteed to improve the solution. If the improvement is ambiguous due to weight uncertainty, the DM is queried.

5. Experimental Evaluation and Results

The algorithms were tested on three matroid problems: Subset Selection (Uniform Matroid), Minimum Spanning Tree (Graphic Matroid), and Job Scheduling (Scheduling Matroid).

Comparison of the uncertainty set refinement after a single query, illustrating the geometric reduction of the weight space.

Key findings include:

  • Query Efficiency: Local Search consistently outperformed the Greedy algorithm in terms of the number of queries required. For a committee selection task with 6 objectives, Local Search required only 46 queries to reach optimality, whereas the Greedy approach needed 99.
  • Computational Complexity: While Local Search is more query-efficient, the Greedy algorithm is significantly faster computationally. The overhead of calculating regret over a local neighborhood is higher than the sequential choices made in the greedy process.
  • Tolerance and Regret: Introducing a tolerance parameter $\delta$ allows for a "near-optimal" solution with a fraction of the queries. Setting $\delta$ to 20% of the initial regret reduced the query count by 50-70% while maintaining an empirical error of less than 0.02%.

6. Conclusion

This work demonstrates that interleaving preference elicitation with optimization is a powerful paradigm for solving combinatorial problems with unknown utilities. By leveraging the structural properties of matroids, the proposed algorithms provide robust performance guarantees. Future work will explore non-linear utility functions and submodular optimization, as well as methods to handle noisy or inconsistent feedback from human decision-makers.

Summary updated

BibTeX
@inproceedings{benabbou2021combining,
  author = {Nawal Benabbou and Cassandre Leroy and Thibaut Lust and Patrice Perny},
  title = {{Combining Preference Elicitation with Local Search and Greedy Search for Matroid Optimization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i14.17452},
}
Figure