Calcul d'approximations intérieures pour la résolution de Max-NCSP

Marc Christie, Jean‐Marie Normand, Charlotte TruchetHAL 2006

TL;DR

This paper introduces a novel algorithm for calculating "inner approximations" of solutions to numerical Constraint Satisfaction Problems (CSPs), specifically focusing on Max-NCSP (where the goal is to satisfy the maximum number of constraints). The approach uses interval arithmetic and a new "inner extension" operator to guarantee that found solutions are indeed valid, offering a more robust way to handle continuous problems compared to traditional methods.

What Problem Does This Paper Address?

Solving Constraint Satisfaction Problems (CSPs) is crucial in many fields like engineering design and robotics. While discrete CSPs are well-studied, continuous CSPs (where variables can take any real value within a range) pose significant challenges. Traditional methods often provide "outer approximations," which guarantee that no real solutions are lost but might include invalid points. For applications requiring absolute certainty, "inner approximations" are needed, ensuring every point within the approximated region is a valid solution. However, calculating these inner approximations for continuous problems, especially when aiming to maximize constraint satisfaction (Max-NCSP), is computationally difficult. This paper tackles this by proposing a method to compute guaranteed inner approximations for Max-NCSP, even when problems are over- or under-constrained.

Methods

The core of the paper lies in developing techniques for calculating inner approximations for continuous CSPs. The authors leverage interval arithmetic, representing numbers as intervals rather than single points. This allows for robust handling of continuous domains and potential rounding errors.

Key methodological contributions include:

  • Inner Extension Operator: A novel operator is introduced that, given a constraint and a "consistent" box (a region where some constraints are satisfied), extends this box inwards to find a larger region where the constraint is certainly satisfied. This is a crucial step for guaranteeing solution validity.
  • Max-NCSP Formulation: The paper defines Max-NCSP for continuous domains and proposes an algorithm that combines constraint propagation (using interval-based AC-3) with the inner extension operator.
  • Hybrid Approach: The authors explore hybridizing their core algorithm with local search (LS) methods extended to intervals. This involves defining concepts like "neighborhood" and "penalty functions" for interval-based configurations. The goal is to use LS to find promising regions faster, potentially improving the efficiency of finding the optimal solution (maximizing satisfied constraints).
  • CPN Characterization: A "CPN" (Certainly, Possibly, Not satisfied) characterization is used to describe how constraints are satisfied within a given box, aiding in pruning the search space.

Datasets

The paper uses "toy problems" for evaluation:

  • Circle-n: Problems defined by n circles in a 2D space (specifically, [-3,3]^2).
  • Sphere-n: Problems defined by n spheres in a 2D space (specifically, [-3,3]^2).

These are synthetic benchmarks designed to test the algorithms' performance on continuous constraint satisfaction scenarios.

Key Insights and Ideas

  • Guaranteed Solutions for Continuous Problems: The primary insight is the development of a method to compute guaranteed inner approximations for continuous Max-NCSP. This is a significant step towards reliable solving of real-world problems where absolute correctness is paramount.
  • Interval Arithmetic as a Foundation: The paper highlights the power of interval arithmetic for robustly handling continuous domains and ensuring correctness, especially in the face of floating-point arithmetic.
  • Inner Extension is Key: The novel "inner extension" operator is critical for moving from potentially valid regions to regions where constraints are certainly satisfied, a fundamental requirement for inner approximations.
  • Local Search for Intervals is Challenging: While the paper proposes an extension of local search to interval domains, the results suggest that this hybrid approach doesn't consistently outperform simpler methods for these specific benchmarks. This points to the inherent difficulties in defining effective neighborhood structures and penalty functions for interval-based local search.

Key Results

The paper presents results comparing three algorithms:

  1. IAMaxNCSP-SplitEval: A naive bisection-based approach.
  2. IAMaxNCSP-Mid: Uses the midpoint of an interval as a representative point.
  3. IAMaxNCSP-CLS: The proposed approach incorporating interval-based local search.

Key findings from Table 1:

  • For the tested "toy problems" (Circle-n and Sphere-n), the IAMaxNCSP-Mid approach (using interval midpoints) generally outperforms the local search (CLS) approach in terms of execution time, especially for larger problems.
  • The SplitEval approach is significantly slower than both Mid and CLS, as expected from a naive bisection strategy.
  • While the CLS approach sometimes finds the optimal solution (maximum satisfied constraints) earlier, its overall execution time is often higher due to the overhead of interval-based local search.
  • The paper notes that the local search approach did not "clearly show its contribution" compared to a naive algorithm, suggesting that its benefits were not as pronounced as hoped for these specific benchmarks.

Limitations and Future Work

  • Local Search Performance: The authors acknowledge that the proposed interval-based local search (CLS) did not consistently outperform simpler methods like the midpoint approach on their toy problems. This suggests that the current implementation of interval local search might not be sufficiently optimized or that the problem instances are not ideal for showcasing its strengths.
  • Métaheuristics for Intervals: The paper explicitly states that developing effective metaheuristics (like tabu search or genetic algorithms) for interval-based search remains an open area for future work. The current implementation of local search is described as "fairly simple."
  • Diversification and Intensification: While random restarts are used for diversification, the paper notes that questions of intensification and diversification for interval-based search need further development.
  • Generalization: The current results are based on simple 2D problems. Extending and validating the approach on more complex, higher-dimensional problems would be a logical next step.

Summary updated

Abstract

Cet article présente un algorithme de calcul de solutions garanties pour des problèmes numériques MaxCSP. Les auteurs proposent une approche qui offre une exploration complète et garantie de l'espace de recherche et identifie l'ensemble des sous-espaces éventuellement disjoints qui satisfont le plus grand nombre de contraintes numériques du CSP. L'implémentation de cet algorithme fournit une approximation intérieure de ces sous-ensembles pour une taille minimale de pavé donnée. L'approche repose sur des méthodes de propagation classiques sur les intervalles (AC-3) et sur un processus d'extension par l'intérieur en n dimensions. Une hybridation avec des méthodes locales de recherche, étendues aux intervalles, est proposée et testée. Les résultats, portant sur des problèmes jouets montrent l'apport par rapport à un algorithme na¨ıf mais ne mettent pas en lumière l'évidence de la contribution des méthodes de recherche locale.
BibTeX
@inproceedings{christie2006calcul,
  author = {Marc Christie and Jean‐Marie Normand and Charlotte Truchet},
  title = {{Calcul d'approximations intérieures pour la résolution de Max-NCSP}},
  booktitle = {HAL},
  year = {2006},
}
Figure