Computing Possibly Optimal Solutions for Multi-Objective Constraint Optimisation with Tradeoffs

Nic Wilson, Abdul Razak, Radu MarinescuIJCAI 2015 · OpenReview

Abstract

Computing the set of optimal solutions for a multiobjective constraint optimisation problem can be computationally very challenging. Also, when solutions are only partially ordered, there can be a number of different natural notions of optimality, one of the most important being the notion of Possibly Optimal, i.e., optimal in at least one scenario compatible with the inter-objective tradeoffs. We develop an AND/OR Branch-and-Bound algorithm for computing the set of Possibly Optimal solutions, and compare variants of the algorithm experimentally.

Introduction

In Multi-Objective Constraint Optimisation (MOCOP), decision-makers often face a "curse of choice." Optimizing for multiple conflicting goals—such as cost, safety, and speed—typically yields a large set of Pareto optimal (undominated) solutions. However, many of these solutions may not be practical under realistic user preferences. This paper addresses the challenge of pruning this set down to Possibly Optimal (PO) solutions: those that are the absolute best under at least one valid set of user tradeoffs consistent with known preferences. While finding PO solutions is computationally more intensive than finding the standard Pareto front, it significantly reduces the cognitive load on human decision-makers.

Methodology

The authors propose a framework that combines decision theory with advanced search techniques. Central to their approach is the use of an AND/OR search space, which exploits problem decomposition to achieve exponential speedups.

Problem representation including utility functions, primal graph, and pseudo tree.

The methodology relies on three main components:

  1. Optimality Operators: The authors define "Possibly Optimal" as a property satisfying Union Decomposition and Additive Decomposition, enabling its use in recursive search.
  2. AND/OR Search Structure: By utilizing the independence of sub-problems (where changes in one variable do not affect another), the algorithm can solve parts of the problem separately. This is represented as an AND/OR tree rather than a traditional linear OR tree.
  3. Pruning Conditions: To manage the search space, the algorithm employs various pruning conditions. The most effective was found to be a "middle-ground" approach using matrix multiplication to check dominance against a set of bounds.
The AND/OR search tree structure used for finding Possibly Optimal solutions.

Experimental Evaluation

The algorithm, Multi-Objective AND/OR Branch-and-Bound (MOAOBB), was tested against standard OR search (MOBB) across several benchmarks:

  • Random Networks: For general performance testing.
  • Vertex Coverings: A classic combinatorial problem, scaled up to 160 variables.
  • Combinatorial Auctions: Modeling resource allocation with varying item values.

Consistent tradeoffs were simulated to represent varying levels of user preference knowledge.

Key Results and Insights

  • Efficiency of PO: The set of Possibly Optimal solutions was found to be significantly smaller—often by a factor of four—than the standard set of undominated solutions (CSD).
  • Impact of Tradeoffs: Interestingly, providing more information about user tradeoffs improved algorithm performance. The additional constraints allowed for more aggressive pruning, speeding up the search.
  • Search Performance: MOAOBB consistently outperformed traditional MOBB, solving more instances within a 20-minute limit. While rigorous pruning (Condition 1) reduced node count the most, an approximate check (Condition 3) proved most efficient in terms of total CPU time.

Conclusion and Future Work

The proposed AND/OR Branch-and-Bound algorithm provides a scalable way to find manageable sets of optimal solutions in multi-objective environments. However, its efficiency is tied to the "induced width" of the problem; highly interconnected variable graphs remain a challenge. Future research could integrate this search method with active preference elicitation, where the system asks the user targeted questions to refine tradeoffs dynamically during the search process.

Summary updated

Abstract

Computing the set of optimal solutions for a multiobjective constraint optimisation problem can be computationally very challenging. Also, when solutions are only partially ordered, there can be a number of different natural notions of optimality, one of the most important being the notion of Possibly Optimal, i.e., optimal in at least one scenario compatible with the inter-objective tradeoffs. We develop an AND/OR Branch-and-Bound algorithm for computing the set of Possibly Optimal solutions, and compare variants of the algorithm experimentally.
BibTeX
@inproceedings{wilson2015computing,
  author = {Nic Wilson and Abdul Razak and Radu Marinescu},
  title = {{Computing Possibly Optimal Solutions for Multi-Objective Constraint Optimisation with Tradeoffs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=Sy-Y7mz_-H},
}
Figure