Reconsidering Mixed Integer Programming and MIP-based Hybrids for Scheduling
Please always quote using this URN: urn:nbn:de:0297-zib-14660
- Despite the success of constraint programming (CP) for scheduling, the much wider penetration of mixed integer programming (MIP) technology into business applications means that many practical scheduling problems are being addressed with MIP, at least as an initial approach. Furthermore, there has been impressive and well-documented improvements in the power of generic MIP solvers over the past decade. We empirically demonstrate that on an existing set of resource allocation and scheduling problems standard MIP and CP models are now competitive with the state-of-the-art manual decomposition approach. Motivated by this result, we formulate two tightly coupled hybrid models based on constraint integer programming (CIP) and demonstrate that these models, which embody advances in CP and MIP, are able to out-perform the CP, MIP, and decomposition models. We conclude that both MIP and CIP are technologies that should be considered along with CP for solving scheduling problems.
Author: | Stefan Heinz, J. Christopher Beck |
---|---|
Document Type: | ZIB-Report |
Tag: | constraint integer programming; constraint programming; cumulative constraint; mixed integer programming; optional activities |
MSC-Classification: | 60-XX PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX) |
65-XX NUMERICAL ANALYSIS / 65Kxx Mathematical programming, optimization and variational techniques / 65K05 Mathematical programming methods [See also 90Cxx] | |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C10 Integer programming | |
Date of first Publication: | 2012/02/11 |
Series (Serial Number): | ZIB-Report (12-05) |
ISSN: | 1438-0064 |
ZIB-Reportnumber: | 12-05 |
Published in: | App. in: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2012), Springer 2012. Lecture Notes in Computer Science, 7298, pp. 211-227 |