Abstract
We study a balanced academic curriculum problem and an industrial steel mill slab design problem. These problems can be modelled in different ways, using both Integer Linear Programming (ILP) and Constraint Programming (CP) techniques. We consider the utility of each model. We also propose integrating the models to create hybrids that benefit from the complementary strengths of each model. Experimental results show that hybridization significantly increases the domain pruning and decreases the run-time on many instances. Furthermore, a CP/ILP hybrid model gives a more robust performance in the face of varying instance data.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Benoist, T., F. Laburthe, and B. Rottembourg. (2001). “Lagrange Relaxation and Constraint Programming Collaborative Schemes for Travelling Tournament Problems.” In Proceedings of CP-AI-OR'01.
Castro, C. and S. Manzano. (2001). “Variable and Value Ordering when Solving Balanced Academic Curriculum Problem.” In Proceedings of the ERCIM WG on Constraints.
Cheng, B.M.W., K.M.F. Choi, J.H.M. Lee, and J.C.K. Wu. (1999). “Increasing Constraint Propagation by Redundant Modelling: An Experience Report.” Constraints 4, 167–192.
El Sakkout, H. and M. Wallace. (2000). “Probe Backtrack Search for Minimal Perturbation in Dynamic Scheduling.” Constraints 5(4), 359–388.
Flener, P., A. Frisch, B. Hnich, Z. Kýzýltan, I. Miguel, and T. Walsh. (2001). “Matrix Modelling.” In Proceedings of the CP-01 Workshop on Modelling and Problem Formulation.International Conference on the Principles and Practice of Constraint Programming.
Frisch, A.M., I. Miguel, and T. Walsh. (2001a). “Modelling a Steel Mill Slab Design Problem.” In Proceedings of the IJCAI-01 Workshop on Modelling and Solving Problems with Constraints.
Frisch, A.M., I. Miguel, and T. Walsh. (2001b). “Symmetry and Implied Constraints in the Steel Mill Slab Design Problem.” In Proceedings of the CP-01 Workshop on Modelling and Problem Formulation.
Geelen, P.A. (1992). “Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems.” In Proceedings of ECAI'92, pp. 31–35.
Ginsberg, M.L., A.J. Parkes, and A. Roy. (1998). “Supermodels and Robustness.” In Proceedings of AAAI/IAAI-98, pp. 334–339.
Hooker, J.N., G. Ottosson, E.S. Thorsteinsson, and H-J. Kim. (1999). “On Integrating Constraint Propagation and Linear Programming for Combinatorial Optimization.” In AAAI/IAAI, pp. 136–141.
Régin, J.-C. (1996). “Generalized Arc Consistency for Global Cardinality Constraints.” In Proceedings of the Eighth National Conference on Aritficial Intelligence, pp. 25–32.
Rodosek, R. and M. Wallace. (1998). “A Generic Model and Hybrid Algorithm for Hoist Scheduling Problems.” In Proceedings of CP-98, pp. 385–399.
Sellmann, M. and T. Fahle. (2001). “CP-Based Lagrangian Relaxation for a Multimedia Application.” In Proceedings of CP-AI-OR'01.
Smith, B.M. (2001). “Dual Models in Constraint Programming.” Research Report 2001.02, University of Leeds (UK), School of Computing.
Van Hentenryck, P. (1999). The OPL Optimization Programming Language. Cambridge, MA: MIT Press.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Hnich, B., Kiziltan, Z., Miguel, I. et al. Hybrid Modelling for Robust Solving. Annals of Operations Research 130, 19–39 (2004). https://doi.org/10.1023/B:ANOR.0000032568.51115.0d
Issue Date:
DOI: https://doi.org/10.1023/B:ANOR.0000032568.51115.0d