Premium
State‐space relaxation procedures for the computation of bounds to routing problems
Author(s) -
Christofides Nicos,
Mingozzi A.,
Toth P.
Publication year - 1981
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230110207
Subject(s) - subgradient method , travelling salesman problem , relaxation (psychology) , mathematical optimization , lagrangian relaxation , recursion (computer science) , integer programming , linear programming relaxation , state space , state (computer science) , computer science , mathematics , combinatorial optimization , routing (electronic design automation) , space (punctuation) , algorithm , psychology , social psychology , computer network , statistics , operating system
It is well‐known that few combinatorial optimization problems can be solved effectively by dynamic programming alone, since the number of vertices of the state space graph is enormous. What we are proposing here is a general relaxation procedure whereby the state‐space associated with a given dynamic programming recursion is relaxed in such a way that the solution to the relaxed recursion provides a bound which could be embedded in general branch and bound schemes for the solution of the problem. This state space relaxation method is analogous to Langrangian relaxation in integer programming. This paper gives a survey of this new methodology, and gives, as examples, applications to the traveling salesman problem (TSP), the time‐constrained TSP and the vehicle routing problem (VRP). Valid state space relaxations are discussed for these problems and several bounds are derived in each case. Subgradient optimization and “state space ascent” are discussed as methods of maximizing the resulting lower bounds. More details of the procedures surveyed in this paper can be found in [2, 3, 4].