Improved CP-Based Lagrangian Relaxation Approach with an Application to the TSP

Raphaël Boudreault, Claude-Guy QuimperIJCAI 2021 · DOI

TL;DR

This paper introduces an enhanced CP-Based Lagrangian Relaxation (CP-LR) approach that improves filtering for optimization problems, specifically the Traveling Salesman Problem (TSP). By strategically modifying Lagrangian multipliers, the authors achieve significantly better pruning of the search space and faster resolution times compared to existing methods.

What Problem Does This Paper Address?

Constraint Programming (CP) is a powerful technique for solving complex optimization problems. A key component of CP solvers is "cost-based filtering," which uses lower bounds derived from relaxed versions of the problem to prune inconsistent variable assignments. Lagrangian relaxation is a common method for obtaining these lower bounds, especially for problems with difficult constraints. CP-Based Lagrangian Relaxation (CP-LR) combines these two ideas: it optimizes Lagrangian multipliers to get tighter bounds while simultaneously using cost-based filtering on the relaxed subproblems.

However, existing CP-LR approaches for the Traveling Salesman Problem (TSP), particularly for the WEIGHTEDCIRCUIT constraint, can be further improved. The challenge is to find ways to increase the number of values filtered from variable domains during the CP-LR process, leading to a more efficient search. This paper aims to address this by proposing an improved CP-LR framework that actively seeks to maximize the filtering effect, not just the tightness of the lower bound.

Methods

The core contribution of this paper is an improved CP-LR framework. This framework introduces a new step before the standard cost-based filtering. This step involves locally modifying the Lagrangian multipliers in a way that aims to increase the number of filtered values. The general idea is to temporarily adjust multipliers to make certain assignments appear inconsistent, even if those multipliers aren't part of the global optimization of the lower bound.

Building on this framework, the authors propose two new algorithms for filtering the WEIGHTEDCIRCUIT constraint in the context of TSP:

  • SIMPLE Algorithm: This algorithm focuses on individual edges and their associated multipliers. It checks if small, localized adjustments to multipliers can force an edge to be either mandatory or forbidden, thereby filtering its corresponding variable. It operates by computing specific values for multiplier adjustments based on the current 1-tree structure and costs.
  • α-SETS Algorithm: This algorithm is more sophisticated and aims to find a set of nodes (an "a-set") whose multipliers can be simultaneously modified to achieve greater filtering. It formulates the problem of finding these multipliers as a system of linear inequalities and iteratively solves for the optimal multiplier adjustment. This algorithm is designed to be more powerful but also more computationally intensive.

The paper also introduces a HYBRID algorithm that combines the SIMPLE and α-SETS approaches, using SIMPLE first and then α-SETS if SIMPLE's filtering is insufficient.

Datasets

The experiments were conducted on symmetric TSP instances from the TSPLIB library. The authors selected instances with sizes ranging from 96 to 500 nodes, which could be solved by their implementation within 8 hours and required at least 100 search nodes.

Key Insights and Ideas

  • Worse Bounds Can Lead to Better Filtering: The paper reinforces the idea that a lower bound that is not necessarily the tightest can sometimes be more effective for filtering in CP-LR. This is because a "worse" bound might reveal more inconsistencies.
  • Local Multiplier Adjustments for Filtering: The core innovation is the realization that multipliers can be temporarily adjusted specifically for filtering purposes, independent of the global multiplier optimization. This allows for targeted pruning of the search space.
  • SIMPLE vs. α-SETS Trade-off: The SIMPLE algorithm offers efficiency and good filtering for individual edges, while the α-SETS algorithm is more powerful but computationally demanding. The HYBRID approach attempts to balance these.
  • The Importance of the 1-Tree Structure: Both algorithms heavily rely on the properties of the minimum 1-tree (a relaxation of the TSP) and its associated costs and structures (support/replacement edges) to derive filtering conditions.

Key Results

The experimental results on TSP instances demonstrate significant improvements:

  • SIMPLE Algorithm: Achieved an average reduction of 15% in the number of search nodes and 18% in solving time compared to the state-of-the-art Choco solver. It reduced solving time for 86% of the instances.
  • HYBRID Algorithm: Showed even more substantial gains, with an average reduction of 36% in search nodes and 30% in solving time compared to Choco. It was successful in reducing solving time for 93% of the instances and was the best-performing method on 79% of them.
  • Pathological Cases: The paper acknowledges that in rare cases (e.g., a280, d198), the number of nodes increased despite additional filtering, a known phenomenon in CP-LR that warrants further investigation.

Limitations and Future Work

  • Computational Cost of α-SETS: The α-SETS algorithm, while powerful, can be computationally expensive, especially for larger instances with many constraints. The paper mentions strategies like limiting the size of the a-set and the number of iterations to manage this.
  • Pathological Cases: The observed increase in search nodes in some instances suggests that the interaction between filtering and search strategies can be complex and requires further study.
  • Future Work: The authors suggest exploring the compatibility of their approach with other TSP solving techniques (like k-cutset and SSSA) and testing their CP-LR framework in other CP-LR contexts beyond the TSP.

Summary updated

BibTeX
@inproceedings{boudreault2021improved,
  author = {Raphaël Boudreault and Claude-Guy Quimper},
  title = {{Improved CP-Based Lagrangian Relaxation Approach with an Application to the TSP}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/190},
}
Figure