The salesman and the tree: the importance of search in CP

International audienceThe traveling salesman problem (TSP) is a challenging optimization problem for CP and OR that has many industrial applications. Its generalization to the degree constrained minimum spanning tree problem (DCMSTP) is being intensively studied by the OR community. In particular , classical solution techniques for the TSP are being progressively generalized to the DCMSTP. Recent work on cost-based relaxations has improved CP models for the TSP. However, CP search strategies have not yet been widely investigated for these problems. The contributions of this paper are twofold. We first introduce a natural generalization of the weighted cycle constraint (WCC) to the DCM-STP. We then provide an extensive empirical evaluation of various search strategies. In particular, we show that significant improvement can be achieved via our graph interpretation of the state-of-the-art Last Conflict heuristic. 1 Motivation The traveling salesman problem (TSP) involves finding a Hamiltonian cycle of minimum weight in a given undirected graph G = (V, E) associated with a weight function w : E → Z. It has been widely investigated by the operational research (OR) community for more than half a century, because it is an important optimization problem with many industrial applications. Its simple structure has enabled the development of general techniques, such as cutting planes, variable fixing, Lagrangian relaxation, and heuristics. These techniques are the key to the success of dedicated solvers (e.g., Concorde [3]), and they can be adapted to a range of optimization problems. Some have even been integrated into general MIP solvers, leading to great improvements in OR. A natural extension of the TSP is the degree constrained minimum spanning tree problem (DCMSTP). Given an undirected weighted graph G = (V, E) associated with a weight function w : E → Z and an integer array d max , the DCMSTP involves finding a minimum spanning tree (MST) of G for which every vertex v ∈ V has at most d max [v] neighbors. In this way, a TSP can be reduced to a DCMSTP in which for any v ∈ V , d max [v] = 2. Consequently, the techniques developed for the TSP have been generalized to the DCMSTP