Skip to main content
SpringerLink
Log in

IBM ILOG CP optimizer for scheduling

20+ years of scheduling with constraints at IBM/ILOG

  • Published:
Constraints Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20

Similar content being viewed by others

Notes

  1. As an indication of the complexity of the modeling language, the reference manual of the last version of ILOG Scheduler was about 1000 pages long.

  2. In fact, time values could have been implemented as floating point variables in CP Optimizer as (1) they are never used to index any internal data structure and (2) the domain of time variables is never enumerated by the propagation, and only very exceptionally by the search (during optimality proof for some specific cases). In general, unlike time-indexed MIP models, the complexity of solving a CP Optimizer scheduling model does not depend on the choice of the time unit.

  3. Note that there is a small abuse of notation here as we allow s = e. This can be used to represent a zero length interval at value s even if in this case the interval [s, e) itself is empty.

  4. In the rest of the paper, we often drop “expression” from “cumul function expression” to increase readability.

  5. The only industrial cases we have seen are applications that were ported from ILOG Scheduler to CP Optimizer, that did not have any explicit objective function (solution quality was ensured by specific heuristics) and required that exactly the same type of solution should be produced by CP Optimizer.

  6. There is similar presolve for simple constraints between presence statuses of two interval variables: when possible those constraints are added into arcs in the logical network.

  7. A contrived better expression is 3 + 2⋆!presenceOf(modes[2])+presenceOf(modes[3]). However it is hard to extend to more than 3 variables and we certainly do not advise users to model alternative costs this way.

References

  1. Aggoun, A., & Beldiceanu, N. (1993). Extending CHIP in order to solve complex scheduling problems. Journal of Mathematical and Computer Modelling, 17, 57–73.

    Article  Google Scholar 

  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. (2016). Mixed-integer and constraint programming techniques for mobile robot task planning. IEEE Robotics and Automation Letters, 1, 500–507.

    Article  Google Scholar 

  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).

  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. (1996). Shortest paths algorithms: theory and experimental evaluation. Mathematical Programming, 73, 129–174.

    MathSciNet  MATH  Google Scholar 

  8. Dechter, R., Meiri, I., & Pearl, J. (1991). Temporal constraint networks. Artificial Intelligence, 49(1-3), 61–96.

    Article  MathSciNet  MATH  Google Scholar 

  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).

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

  13. Gedik, R., Kirac, E., Milburn, A.B., & Rainwater, C. (2017). A constraint programming approach for the team orienteering problem with time windows. Computers & Industrial Engineering, 107, 178–195.

    Article  Google Scholar 

  14. Gedik, R., Rainwater, C., Nachtmann, H., & Pohlb, E. (2016). Analysis of a parallel machine scheduling problem with sequence dependent setup times and job availability intervals. European Journal of Operational Research, 251, 640–650.

    Article  MathSciNet  MATH  Google Scholar 

  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. (2016). Flexible job shop scheduling problem with parallel batch processing machines: MIP and CP approaches. Computers & Industrial Engineering, 102, 160–165.

    Article  Google Scholar 

  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, J.N. (2007). Planning and scheduling by logic-based benders decomposition. Operations Research, 55(3), 588–602.

    Article  MathSciNet  MATH  Google Scholar 

  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).

  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).

  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).

  26. Kolisch, R., & Sprecher, A. (1996). PSPLIB - A project scheduling problem library. European Journal of Operational Research, 96, 205–216.

    Article  MATH  Google Scholar 

  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.

  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).

  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).

  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. (2016). Temporal linear relaxation in IBM ILOG CP optimizer. Journal of Scheduling, 19(4), 391–400.

    Article  MathSciNet  MATH  Google Scholar 

  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. (2016). Mathematical modeling of the astronaut training scheduling. Management of Large Systems, 63, 129–154. (in Russian).

    Google Scholar 

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

    Article  Google Scholar 

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

    Google Scholar 

  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).

  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. (2016). Evaluating the solution performance of IP and CP for berth allocation with time-varying water depth. Transportation Research, 87, 167–185.

    Article  Google Scholar 

  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. (2017). 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.

    MathSciNet  MATH  Google Scholar 

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

    Google Scholar 

  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.

  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).

Download references

Author information

Authors and Affiliations

  1. IBM France, 9 rue de Verdun, BP 85, 94253, Gentilly, France

    Philippe Laborie & Jérôme Rogerie

  2. IBM France, 1681 Route des Dolines, Les Taissounières, 06560, Valbonne, France

    Paul Shaw

  3. IBM Czechia, V Parku 2294/4, Praha 4 Chodov, 14800, Czech Republic

    Petr Vilím

Authors
  1. Philippe Laborie
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jérôme Rogerie
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Paul Shaw
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Petr Vilím
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Philippe Laborie.

Additional information

This article belongs to the Topical Collection: 20th Anniversary Issue

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Laborie, P., Rogerie, J., Shaw, P. et al. IBM ILOG CP optimizer for scheduling. Constraints 23, 210–250 (2018). https://doi.org/10.1007/s10601-018-9281-x

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10601-018-9281-x

Keywords

Search

Navigation