×

zbMATH — the first resource for mathematics

Solving TSP through the integration of OR and CP techniques. (English) Zbl 0990.90553
Wallace, Mark (ed.) et al., CP98. Workshop on large scale combinatorial optimisation and constraints. Pisa, Italy, October 30, 1998. Amsterdam: Elsevier, Electron. Notes Discrete Math. 1, 13-25, electronic only (1999).
Summary: Constraint programming techniques have been successfully applied to several combinatorial optimization problems. One of their advantages is the availability of complex global constraints performing efficient propagation and interacting with each other through shared variables. However, Constraint Programming techniques have shown their limitations in dealing with objective functions, since they are usually able to prune only few levels of the search tree when most decision variables have been already instantiated. In this paper, we integrate well known Operations Research (OR) techniques within global constraints, thus obtaining optimization oriented constraints. The idea is to prune the search space using reduction rules based on lower bound and reduced costs calculation. The interest of integrating efficient well-known OR algorithms into CP is mainly due to the CP domain reduction mechanism which can be seen as a communication channel among different constraints.
We have applied this technique to symmetric and asymmetric Travelling Salesman Problem (TSP) instances both because the TSP is an interesting problem arising in many real life applications, and because pure CP techniques lead to disappointing results for this problem. We have tested the proposed optimization constraints using the ILOG Solver library. Computational results on benchmarks available from literature, and comparison with related approaches will also be described in the paper.
For the entire collection see [Zbl 0968.90003].

MSC:
90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
90C10 Integer programming
Software:
CPLEX
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Balas, E.; Zemel, E., An algorithm for large zero-one knapsack problems, Operations research, 28, 1130-1154, (1980) · Zbl 0449.90064
[2] Caseau, Y.; Laburthe, F., Solving small TSPs with constraints, ()
[3] Dantzig, G.B., Discrete variable extremum problems, Operations research, 5, 266-277, (1957) · Zbl 1414.90353
[4] Fisher, M.L., The Lagrangian relaxation method for solving integer programming problems, Management science, 27, 1-18, (1981) · Zbl 0466.90054
[5] Graham, R.L.; Knuth, D.E.; Patashnik, O., ()
[6] Horowitz, E.; Sahni, S.; Rajasekaran, S., Computer algorithms: C++, (1997), Computer Science Press
[7] Jaffar, J.; Michaylov, S.; Stuckey, P.J.; Yap, R., The CLP(R) language and system, ACM transactions on programming languages and systems, 14, 3, 339-395, (July 1992)
[8] Maculan, N., Relaxation lagrangienne: le probleme du knapsack, 0-2. INFOR (Canadian journal of operational research and information processing), 21, 315-327, (1983) · Zbl 0527.90073
[9] Martello, S.; Toth, P., ()
[10] Pesant, G.; Gendreau, M., A view of local search in constraint programming, Principles and practice of constraint programming - CP96, 353-366, (1996)
[11] H. Simonis. “A problem classification scheme for finite domain constraint solving.” Proceedings of the CP’96 Workshop on Constraint Programming Applications, 1-25, 1996.
[12] Van Hentenryck, P., ()
[13] M. Wallace. Survey: Practical applications of constraint programming. Technical Report, IC Parc, September 1995.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.