Multi-Objective 3-SAT with Survey-Propagation

Cyril Furtlehner, Marc Schoenauer2010

TL;DR

This paper introduces a novel message-passing algorithm, an extension of Survey-Propagation (SP), to tackle multi-objective optimization problems, specifically the bi-objective 3-SAT problem. The method aims to efficiently sample the Pareto set, enabling informed decision-making in complex optimization scenarios.

What Problem Does This Paper Address?

Many real-world optimization problems are inherently multi-objective, meaning they involve optimizing several conflicting goals simultaneously. The challenge lies in finding the "Pareto set," which represents the set of solutions where no objective can be improved without degrading at least one other objective. Traditional optimization methods often struggle with this, especially in combinatorial problems like SAT (Satisfiability), where the search space is vast. While message-passing algorithms like Survey-Propagation (SP) have been successful for single-objective SAT problems, their application to multi-objective settings has been limited. This paper bridges this gap by extending SP to the multi-objective domain, specifically for the bi-objective 3-SAT problem.

Methods

The core contribution is the adaptation of the Survey-Propagation (SP) algorithm for multi-objective optimization. The authors introduce a "deformed" SP equation that locally encodes Pareto trade-offs. This involves modifying the message-passing equations to account for conflicting requirements from different objectives. They propose a heuristic that combines clause elimination with variable decimation, a standard technique in SP, to explore different regions of the Pareto front. A key aspect is the investigation of how these deformed equations comply with basic Belief-Propagation (BP) properties, leading to the formulation of a Markov Random Field (MRF) that approximates the Pareto set. The paper also discusses a generalized approach for multi-objective contexts, incorporating a penalty factor to manage conflicts between objectives.

Datasets

The paper uses artificial bi-objective 3-SAT problems for evaluation. These problems are generated with varying clause densities and up to 10^5 variables. The authors do not introduce a new benchmark dataset but rather adapt a well-known problem class (random 3-SAT) to a multi-objective setting.

Key Insights and Ideas

  • Extending SP to Multi-Objective: The paper demonstrates that message-passing algorithms, specifically SP, can be successfully adapted to multi-objective optimization by modifying their core equations to handle local Pareto trade-offs.
  • Local Pareto Encoding: The key innovation is the ability to encode Pareto dominance relations at a local level within the message-passing framework, allowing the algorithm to navigate conflicting objectives.
  • MRF for Pareto Set Approximation: The authors show that the multi-objective SP equations can be associated with a Markov Random Field (MRF) that approximates the Pareto set, providing a theoretical foundation for the approach.
  • Heuristic for Pareto Front Exploration: The proposed heuristic, combining clause elimination and variable decimation, effectively samples different parts of the Pareto front, offering a practical way to explore trade-offs.

Key Results

The paper presents numerical experiments on artificial bi-objective 3-SAT problems. The deformed SP equations are used to estimate the Pareto front. The results show that the approach can find Pareto solutions that are competitive with existing methods like SP-Y (a multi-objective SAT solver) for certain problem instances. The performance is shown to scale reasonably well with problem size for clause densities below a critical threshold.

Limitations and Future Work

The authors acknowledge that the proposed method might not achieve optimal performance and suggest several areas for improvement. These include:

  • Simplifying Assumptions: The MRF definition or the SP equations might still contain simplifying assumptions that limit optimality.
  • Backtracking Techniques: Incorporating backtracking during the clause elimination and decimation stages could potentially improve results.
  • Generalization to More Objectives: The current work focuses on bi-objective problems; extending it to problems with more than two objectives is a natural next step.
  • Application to Other Problems: The authors believe the approach is generic and can be applied to other multi-objective constraint satisfaction problems.

Summary updated

Abstract

International audience
BibTeX
@misc{furtlehner2010multi,
  author = {Cyril Furtlehner and Marc Schoenauer},
  title = {{Multi-Objective 3-SAT with Survey-Propagation}},
  year = {2010},
}
Figure