Solving Resource Allocation/Scheduling Problems with Constraint Integer Programming
Please always quote using this URN: urn:nbn:de:0297-zib-12691
- Constraint Integer Programming (CIP) is a generalization of mixed-integer programming (MIP) in the direction of constraint programming (CP) allowing the inference techniques that have traditionally been the core of \P to be integrated with the problem solving techniques that form the core of complete MIP solvers. In this paper, we investigate the application of CIP to scheduling problems that require resource and start-time assignments to satisfy resource capacities. The best current approach to such problems is logic-based Benders decomposition, a manual decomposition method. We present a CIP model and demonstrate that it achieves performance competitive to the decomposition while out-performing the standard MIP and CP formulations.
Author: | Stefan Heinz, J. Christopher Beck |
---|---|
Document Type: | ZIB-Report |
Tag: | |
MSC-Classification: | 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: | 2011/04/19 |
Series (Serial Number): | ZIB-Report (11-14) |
ZIB-Reportnumber: | 11-14 |