IBM ILOG CP optimizer for scheduling. 20+ years of scheduling with constraints at IBM/ILOG.

*(English)*Zbl 1400.90169Summary: IBM ILOG CP Optimizer is a generic CP-based system to model and solve scheduling problems. It provides an algebraic language with simple mathematical concepts to capture the temporal dimension of scheduling problems in a combinatorial optimization framework. CP Optimizer implements a model-and-run paradigm that vastly reduces the burden on the user to understand CP or scheduling algorithms: modeling is by far the most important. The automatic search provides good performance out of the box and it is continuously improving. This article gives a detailed overview of CP Optimizer for scheduling: typical applications, modeling concepts, examples, automatic search, tools and performance.

##### MSC:

90B35 | Deterministic scheduling theory in operations research |

90C27 | Combinatorial optimization |

90-03 | History of operations research and mathematical programming |

01A61 | History of mathematics in the 21st century |

90-04 | Software, source code, etc. for problems pertaining to operations research and mathematical programming |

PDF
BibTeX
XML
Cite

\textit{P. Laborie} et al., Constraints 23, No. 2, 210--250 (2018; Zbl 1400.90169)

Full Text:
DOI

##### References:

[1] | Aggoun, A; Beldiceanu, N, Extending CHIP in order to solve complex scheduling problems, Journal of Mathematical and Computer Modelling, 17, 57-73, (1993) |

[2] | Booth, K., Nejat, G., & Beck, C. (2016). A constraint programming approach to multi-robot task allocation and scheduling in retirement homes. In Proceedings of the 22th international conference on principles and practice of constraint programming (CP 2016) (pp. 539-555). |

[3] | Booth, K; Tran, T; Nejat, G; Beck, C, Mixed-integer and constraint programming techniques for mobile robot task planning, IEEE Robotics and Automation Letters, 1, 500-507, (2016) |

[4] | Brafman, R.I. (2001). A simplifier for propositional formulas with many binary clauses. In Proceedings of the 17th international joint conference on artificial intelligence (IJCAI 2001) (pp. 515-522). |

[5] | Cappart, Q., & Schaus, P. (2017). Rescheduling railway traffic on real time situations using time-interval variables. In Proceedings of the 14th international conference on integration of AI and OR techniques in constraint programming (CPAIOR 2017) (pp. 312-327). · Zbl 06756596 |

[6] | Cesta, A., & Oddi, A. (1996). Gaining efficiency and flexibility in the simple temporal problem. In Proceedings of the 3rd international workshop on temporal representation and reasoning (TIME 1996) (pp. 45-50). |

[7] | Cherkassky, B; Goldberg, A; Radzic, T, Shortest paths algorithms: theory and experimental evaluation, Mathematical Programming, 73, 129-174, (1996) · Zbl 0853.90111 |

[8] | Dechter, R; Meiri, I; Pearl, J, Temporal constraint networks, Artificial Intelligence, 49, 61-96, (1991) · Zbl 0737.68070 |

[9] | Dvořák, J., Heller, M., & Hanzálek, Z. (2017). Makespan minimization of Time-Triggered traffic on a TarticleTarticleEthernet network. In Proceedings of the IEEE 13th international workshop on factory communication systems (WFCS 2017). |

[10] | Frank, J., Do, M., & Tran, T.T. (2016). Scheduling ocean color observations for a GEO-Stationary satellite. In Proceedings of the 26th international conference on automated planning and scheduling (ICAPS 2016). |

[11] | Gay, S., Hartert, R., & Schaus, P. (2015). Simple and scalable time-table filtering for the cumulative constraint. In Proceedings of the 21st international conference on principles and practice of constraint programming (CP 2015) (pp. 149-157). · Zbl 1459.90093 |

[12] | GECODE: Gecode Toolkit (2016). Available at http://www.gecode.org/. |

[13] | Gedik, R; Kirac, E; Milburn, AB; Rainwater, C, A constraint programming approach for the team orienteering problem with time windows, Computers & Industrial Engineering, 107, 178-195, (2017) |

[14] | Gedik, R; Rainwater, C; Nachtmann, H; Pohlb, E, Analysis of a parallel machine scheduling problem with sequence dependent setup times and job availability intervals, European Journal of Operational Research, 251, 640-650, (2016) · Zbl 1346.90346 |

[15] | Giles, K., & van Hoeve, W.J. (2016). Solving a supply-delivery scheduling problem with constraint programming. In Proceedings of the 22th international conference on principles and practice of constraint programming (CP 2016) (pp. 602-617). |

[16] | Godard, D., Laborie, P., & Nuijten, W. (2005). Randomized large neighborhood search for cumulative scheduling. In Proceedings of the 15th international conference on automated planning and scheduling (ICAPS 2005) (pp. 81-89). |

[17] | Gregory, A., & Majumdar, S. (2016). Energy aware resource management for MapReduce jobs with service level agreements in cloud data centers. In Proceedings of the IEEE international conference on computer and information technology (CIT 2016) (pp. 568-577). |

[18] | Ham, A; Cakici, E, Flexible job shop scheduling problem with parallel batch processing machines: MIP and CP approaches, Computers & Industrial Engineering, 102, 160-165, (2016) |

[19] | Han, J., Yuan, Z., Han, Y., Peng, C., Liu, J., & Li, G. (2017). An adaptive scheduling algorithm for heterogeneous Hadoop systems. In Proceedings of the IEEE/ACIS 16th international conference on computer and information science (ICIS 2017) (pp. 845-850). |

[20] | Hooker, JN, Planning and scheduling by logic-based benders decomposition, Operations Research, 55, 588-602, (2007) · Zbl 1167.90512 |

[21] | IBM: ILOG CPLEX Optimization Studio 12.7.1: CP Optimizer Online Documentation (2017). Available at http://ibm.biz/COS1271Documentation. |

[22] | Kinable, J. (2016). A reservoir balancing constraint with applications to bike-sharing. In Proceedings of the 13th international conference on integration of AI and OR techniques in constraint programming (CPAIOR 2016) (pp. 216-228). · Zbl 06598667 |

[23] | Kinable, J., van Hoeve, W.J., & Smith, S. (2016). Optimization models for a real-world snow plow routing problem. In Proceedings of the 13th international conference on Integration of AI and OR techniques in constraint programming (CPAIOR 2016) (pp. 229-245). · Zbl 06598668 |

[24] | Kinnunen, T. (2016). Cost-efficient vacation planning with variable workforce demand and manpower. Technical report, Aalto University School of Science. |

[25] | Kizilay, D., Eliiyi, D.T., & Van Hentenryck, P. (2018). Constraint and mathematical programming models for integrated port container terminal operations. In Proceedings of the 15th international conference on the integration of constraint programming, artificial intelligence, and operations research (CPAIOR 2018). · Zbl 06982403 |

[26] | Kolisch, R; Sprecher, A, PSPLIB - A project scheduling problem library, European Journal of Operational Research, 96, 205-216, (1996) · Zbl 0947.90587 |

[27] | Kramer, L.A., Barbulescu, L.V., & Smith, S.F. (2007). Understanding performance tradeoffs in algorithms for solving oversubscribed scheduling. In Proceedings of the 22nd AAAI conference on artificial intelligence (AAAI 2007) (pp. 1019-1024). |

[28] | Ku, W.Y., & Beck, J.C. (2016). Mixed integer programming models for job shop scheduling: a computational analysis. Computers & Operations Research. · Zbl 1349.90365 |

[29] | Laborie, P. (2009). IBM ILOG CP Optimizer for detailed scheduling illustrated on three problems. In Proceedings of the 6th international conference on integration of AI and OR techniques in constraint programming for combinatorial optimization problems (CPAIOR 2009) (pp. 148-162). |

[30] | Laborie, P. (2014). An optimal iterative algorithm for extracting MUCs in a black-box constraint network. In Proceedings of the 21st European conference on artificial intelligence (ECAI 2014) (pp. 1051-1052). |

[31] | Laborie, P. (2018). Objective landscapes for constraint programming. In Proceedings of the 15th international conference on the integration of constraint programming, artificial intelligence, and operations research (CPAIOR 2018). · Zbl 06982406 |

[32] | Laborie, P. (2018). An update on the comparison of MIP, CP and hybrid approaches for mixed resource allocation and scheduling. In Proceedings of the 15th international conference on the integration of constraint programming, artificial intelligence, and operations research (CPAIOR 2018). · Zbl 06982407 |

[33] | Laborie, P., & Godard, D. (2007). Self-adapting large neighborhood search: application to single-mode scheduling problems. In Baptiste, P., Kendall, G., Munier-Kordon, A., & Sourd, F. (Eds.) Proceedings of the 3rd multidisciplinary international conference on scheduling: Theory and applications (MISTA 2007) (pp. 276-284). Paris. |

[34] | Laborie, P., & Messaoudi, B. (2017). New results for the GEOCAPE observation scheduling problem. In Proceedings of the 27th international conference on automated planning and scheduling (ICAPS 2017) (pp. 382-390). |

[35] | Laborie, P., & Rogerie, J. (2008). Reasoning with conditional time-intervals. In Proceedings of the 21th international Florida artificial intelligence research society conference (FLAIRS 2008) (pp. 555-560). |

[36] | Laborie, P; Rogerie, J, Temporal linear relaxation in IBM ILOG CP optimizer, Journal of Scheduling, 19, 391-400, (2016) · Zbl 1347.90044 |

[37] | Laborie, P., Rogerie, J., Shaw, P., & Vilím, P. (2009). Reasoning with conditional time-intervals, part II: an algebraical model for resources. In Proceedings of the 22th international Florida artificial intelligence research society conference (FLAIRS 2009) (pp. 201-206). |

[38] | Lazarev, A; Bronnikov, S; Gerasimov, A; Musatova, E; Petrov, A; Ponomarev, K; Kharlamov, M; Khusnullin, N; Yadrentsev, D, Mathematical modeling of the astronaut training scheduling, Management of Large Systems, 63, 129-154, (2016) |

[39] | Le Pape, C, Implementation of resource constraints in ILOG schedule: a library for the development of constraint-based scheduling systems, Intelligent Systems Engineering, 3, 55-66, (1994) |

[40] | Morton, T., & Pentico, D. (1993). Heuristic scheduling systems. NY: Wiley. |

[41] | Mossige, M. CSPLib problem 073: Test scheduling problem. http://www.csplib.org/Problems/prob073. |

[42] | Policella, N., Cesta, A., Oddi, A., & Smith, S. (2004). Generating robust schedules through temporal flexibility. In Proceedings of the 14th international conference on automated planning and scheduling (ICAPS 2004) (pp. 209-218). · Zbl 1152.90460 |

[43] | Prud’homme, C., Fages, J.G., & Lorca, X. (2016). Choco documentation. TASC, INRIA Rennes, LINA CNRS UMR 6241, COSLING S.A.S. http://www.choco-solver.org. |

[44] | Puget, J.F. (2004). Constraint programming next challenge: simplicity of use. In Proceedings of the 10th international conference on principles and practice of constraint programming (CP 2004) (pp. 5-8). |

[45] | Qin, T; Du, Y; Sha, M, Evaluating the solution performance of IP and CP for berth allocation with time-varying water depth, Transportation Research, 87, 167-185, (2016) |

[46] | Rainwater, C., Nachtmann, H., & Adbesh, F. (2016). Optimal Dredge Fleet Scheduling within Environmental Work Windows. Technical report, Maritime Transportation Research and Education Center. |

[47] | Roofigari-Esfahan, N., & Razavi, S. (2017). Uncertainty-aware linear schedule optimization: a space-time constraint-satisfaction approach. Journal of Construction Engineering and Management, 143(5). |

[48] | Schmitt, M., & Stuetz, P. (2016). Perception-oriented cooperation for multiple UAVs in a perception management framework: system concept and first results. In Proceedings of the IEEE/AIAA 35th digital avionics systems conference (DASC 2016) (pp. 1-10). |

[49] | Shaw, P. (1998). Using constraint programming and local search methods to solve vehicle routing problems. In Proceedings of the 4th international conference on principles and practice of constraint programming (CP 1998) (pp. 417-431). |

[50] | Tran, T; Vaquero, T; Nejat, G; Beck, C, Robots in retirement homes: applying off-the-shelf planning and scheduling to a team of assistive robots, Journal of Artificial Intelligence Research, 58, 523-590, (2017) · Zbl 06703652 |

[51] | Van Hentenryck, P. (1999). The OPL optimization programming language. Cambridge: MIT Press. |

[52] | Vilím, P. (2007). Global constraints in scheduling. Ph.D. thesis, Charles University in Prague, Faculty of Mathematics and Physics, Department of Theoretical Computer Science and Mathematical Logic, KTIML MFF, Universita Karlova, Malostranské náměstí 2/25, 118 00 Praha 1, Czech Republic. http://vilim.eu/petr/disertace.pdf. |

[53] | Vilím, P. (2011). Timetable edge finding filtering algorithm for discrete cumulative Resources. In Achterberg, T., & Beck, J. (Eds.) Proceedings of the 8th international conference on integration of AI and OR techniques in constraint programming for combinatorial optimization problems (CPAIOR-2011), Lecture notes in computer science (Vol. 6697, pp. 230245). Berlin: Springer. · Zbl 1302.90090 |

[54] | Vilím, P., Laborie, P., & Shaw, P. (2015). Failure-directed search for constraint-based scheduling. In Proceedings of the 12th international conference on integration of AI and OR techniques in constraint programming (CPAIOR 2015) (pp. 437-453). · Zbl 1459.90107 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.