Abstract
In recent years, a growing number of attempts have been performed in order to integrate well known Operations Research (OR) techniques in Constraint Programming (CP) tools. The aim of the integration is to maintain the modelling facilities of the CP paradigm, while improving its performances by exploiting effective OR techniques. In our previous work, we proposed the use of optimization constraints [9], embedding a linear relaxation of the constraint itself and performing pruning on the basis of costs. In particular, domain values can be removed whenever it can be shown that their assignment will necessarily lead to solutions worse than the best solution found. In this setting, the use of cutting planes in global constraints allows to tighten the relaxation so as to infer more accurate bounds on the problem. We propose different ways of using cutting-planes in optimization constraints achieving different levels of tightness of the integration and pruning power. Even if the proposed technique is general, we use as testing application the Travelling Salesman Problem (TSPs) and its time constrained variant. Computational results compare different relaxations in terms of pruning achieved and computational complexity.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
N. Ascheuer, M. Fischetti, and M. Grötschel. “Solving atsp with time windows by branch-and-cut”, Tech. Report ZIB Berlin, 1999.
E. Balas, M. Fischetti and W. Pulleyblank. “The precedence constrained asymmetric travelling salesman problem”, Mathematical Programming 68, 241–265, 1995.
P. Barth and A. Bockmayr, “Finite Domain and Cutting Plane Techniques in CLP(PB)”, in Proceedings of the 14th International Conference on Logic Programming-ICLP’95, MIT Press, 1995.
A. Bockmayr and T. Kasper, “Branch-and-Infer: A Unifying Framework for Integer and Finite Domain Constraint Programming”, INFORMS J. Computing, 10(3), p. 287–300, 1998.
G. Carpaneto, S. Martello and P. Toth. “Algorithms and codes for the assignment problem”, in Annals of Operations Research, 13, pp. 193–223, 1988.
M. Fischetti and P. Toth, “A Polyhedral Approach to the Asymmetric Traveling Salesman Problem”, Management Science, 43, pp. 1520–1536, 1997.
F. Focacci, P. Laborie and W. Nuijten, “Solving Scheduling Problems with Setup Times and Alternative Resources”, Proceedings of the Fifth International Conference on Artificial Intelligence Planning and Scheduling (AIPS2000), pp. 92–101, April 2000.
F. Focacci, A. Lodi and M. Milano, “Solving TSP with Time Windows with Constraints”, in De Schreye, D., Ed., Proceedings of the 16th International Conference on Logic Programming-ICLP’99, pp. 515–529, MIT Press, 1999.
F. Focacci, A. Lodi and M. Milano, “Cost-based domain filtering”, in Proceedings of the International Conference on Principles and Practice of Constraint Programming CP’99, LNCS 1713, Springer Verlag, pp. 189–203, 1999.
F. Focacci, A. Lodi, M. Milano and D. Vigo, “Solving TSPs through the integration of CP and OR techniques”, in Proceedings of Workshop on Hybrid Approaches to Large Scale Combinatorial Optimization Problems, in Electronic Notes of Discrete Mathematics, 1, 1999.
F. Focacci, A. Lodi and M. Milano, “Integration of CP and OR methods for Matching Problems”, in Proceedings of Workshop on Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimization Problems, Ferrara, 1999.
R. E. Gomory, “Outline of an Algorithm for Integer Solution to Linear Programs”, Bulletin Amer. Math. Soc. 64,5, 1958.
J. N. Hooker, “Generalized Resolution and Cutting Planes”, Annals of Operations Research, 12, pp. 217–239, 1988.
J. N. Hooker, “Constraint Satisfaction Methods for Generating Valid Cuts”, in Advances in Computational and Stochastic Optimization, Logic Programming and Heuristic Search, Kluwer, pp. 1–30, 1997.
M. Jünger, G. Rinaldi and S. Thienel, “MINCUT, software package”, Universität zu Köln, 1996.
K. Marriott and P. J. Stuckey, Programming with Constraints, MIT Press, 1998.
G. Ottoson, E. S. Thorsteinsson and J. N. Hooker, Mixed Global constraints and inference in hybrid CLP-IP solvers, in Proc. CP99 Post Conference Workshop on LSCO and Constraints, Electronic Notes in Discrete Mathematics, Elsevier Science, 1999.
M. Padberg and G. Rinaldi, “Optimization of a 532-city symmetric traveling salesman problem by branch-and-cut”, Oper. Res. Lett., 6, pp. 1–7, 1987.
M. Padberg and G. Rinaldi, “An Efficient Algorithm for the Minimum Capacity Cut Problem”, Mathematical Programming, 47, pp. 19–36, 1990.
G. Pesant, M. Gendreau, J. Y. Potvin and J. M. Rousseau, “An Exact Constraint logic programming algorithm for the travelling salesman problem with time windows, Transportation Science, 32(1), pp. 12–29, 1998.
P. Refalo, “Tight cooperation and its application in piecewise linear optimization”, Proceedings of the International Conference on Principles and Practice of Constraint Programming CP’99, Springer Verlag, 1999.
M. M. Solomon, Algorithms for the Vehicle Routing and scheduling problem with time window constraints, Operations Research, 35, pp. 254–265, 1987.
ILOG Solver 4.4 User’s Manual, ILOG Planner 3.2 User’s Manual, ILOG Scheduler 4.4 User’s Manual, 1999.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Focacci, F., Lodi, A., Milano, M. (2000). Cutting Planes in Constraint Programming: An Hybrid Approach. In: Dechter, R. (eds) Principles and Practice of Constraint Programming – CP 2000. CP 2000. Lecture Notes in Computer Science, vol 1894. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45349-0_15
Download citation
DOI: https://doi.org/10.1007/3-540-45349-0_15
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41053-9
Online ISBN: 978-3-540-45349-9
eBook Packages: Springer Book Archive