M. Sellmann showed that CP-based Lagrangian relaxation gave good results but the interactions between the filtering algorithms and the Lagrangian multipliers were quite difficult to understand. In other words, it is difficult to determine when filtering algorithms should be triggered. There are two main reasons for this: the best multipliers do not lead to the best filtering and each filtering disrupts the solving of the Lagrangian multiplier problem. In this paper, we study these interactions for the Traveling Salesman Problem (TSP) because the resolution of the TSP in CP is mainly based on a Lagrangian relaxation. We propose to match the calls to the filtering algorithms with the strong variations of the objective value. In addition, we try to avoid oscillations of the objective function. We introduce Scope Sizing Subgradient algorithm, denoted by SSSA, which is an adaptive algorithm, that implements this idea. We experimentally show the advantage of this approach by considering different search strategies or additional constraints. A gain of a factor of two in time is observed compared to the state of the art.
展开▼
