Abstract
The aim of this paper is to demonstrate that CP could be a better candidate than MIP for solving the master problem within a Benders decomposition approach. Our demonstration is based on a case study of a workforce scheduling problem encountered in a large call center of Bouygues Telecom, a French mobile phone operator. Our experiments show that CP can advantageously replace MIP for the implementation of the master problem due to its greater ability to efficiently manage a wide variety of constraints such as the ones occurring in time tabling applications.
This is a preview of subscription content, log in via an institution to check access.
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
J. F. Benders. Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4:238–252, 1962.
A. M. Geoffiïon and G. W. Graves. Multicomodity distribution system design by Benders decomposition. Management Science, 20:822–844, 1974.
M. Minoux. Network Synthesis and Optimum Network Design Problems: Models, Solution Methods and Applications. Network, 19:313–360, 1989.
N. Kagan and R. N. Adams. A Benders’ Decomposition Approach To The Multi-Objective Distribution Planning Problem. International Journal of Electrical Power & Energy Systems, 15(5):259–271,1993.
R.M. Wollmer. Two stage linear programming under uncertainty with 0-1 first stage variables. Mathematical Programming, 19:279–288, 1980.
J.N. Hooker and G. Ottosson. Logic-based Benders decomposition. Mathematical Programming, to appear in November 2001.
A. Eremin and M. Wallace. Hybrid Benders decomposition algorithms in constraint logic programming. CP 2001, LNCS, 2239:1–15, 2001.
E. S. Thornsteinsson. Branch-and-Check: a Hybrid Framework Integrating Mixed Integer Programming and Constraint Logic Programming. In Proceedings of CP-01, Lecture Notes in Computer Science, 2239:16–30. Springer-Verlag, November 2001.
V. Jain, I. E. Grossmann. Algorithms for Hybrid MILP/CP Models for a Class of Optimization Problems. In Informs Journal On Computing, 13:258–276, 2001.
C. Berge and A. Ghouila-Houri. Programming, Games and Transportation Networks. Wiley, New York, 1962.
V. Chvatal. Linear Programming. W. H. Freeman, New York, 1983.
XPRESS-MP. http://www.dash.co.uk, 2002.
F. Laburthe and the OCRE project team. CHOCO: Implementing a CP kernel. CP 2000 Workshop Program, 2000.
Y. Caseau, F.-X. Josset, F. Laburthe. Claire: Combining Sets, Search and Rules to Better Express Algorithms. Proceeding of ICLP’99, MIT Press, New Mexico, 1999.
N. Beldiceanu and E. Contejean. Introducing Global Constraints in CHIP. Mathematical and Computer Modeling, 20(2):97–123, 1994.
A. Bockmayr, N. Pisaruk and A. Aggoun. Network Flow Problems in Constraint Programming. CP 2001, LNCS, 2239:196–210, 2001.
R.K. Ahuja, T.L. Magnanti and J.B. Orlin. Network Flows: theory, algorithms and applications. Prentice Hall, 1993.
P. Van Hentenryck. Constraint Satisfaction in Logic Programming. The MIT Press, 1989.
A.V. Goldberg and R.E. Tarjan. A new approach to the maximum flow problem. Proceedings of the 18 th ACMsymposium on Theory of Computing, 1986.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Benoist, T., Gaudin, E., Rottembourg, B. (2002). Constraint Programming Contribution to Benders Decomposition: A Case Study. In: Van Hentenryck, P. (eds) Principles and Practice of Constraint Programming - CP 2002. CP 2002. Lecture Notes in Computer Science, vol 2470. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46135-3_40
Download citation
DOI: https://doi.org/10.1007/3-540-46135-3_40
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44120-5
Online ISBN: 978-3-540-46135-7
eBook Packages: Springer Book Archive