2IMI25 - Constraint programming

Constraint Programming (CP) is a widely used paradigm to model and solve combinatorial optimization problems. Being able to model and solve combinatorial optimization problems is a skill that is broadly valued, by big corporations like Google, IBM, SAP, Oracle, Microsoft, but also by a large number of smaller companies and start-ups. CP is widely used both in consulting, where an optimization consultant solves a specific problem for one customer, and in software development where it is used in products that cater to a broad set of customers. Being able to model and solve problems through CP is a very valuable addition to being able to model and solve problems by way of Mathematical Programming. As such combining this course with course 2WO09 - Modelleren van LP-problemen, gives students a great background in modeling and solving combinatorial optimization problems. The course will start by presenting the foundations of Constraint Programming in detail. Students will learn about variables, constraints, domains, constraint propagation, arc-consistency, global propagation and much more. They will then get hands-on experience by modeling a variety of CP problems. The tool used for that is IBM ILOG CPLEX Optimization Studio (COS) together with the OPL modeling language. As such students will learn how to use the COS IDE and the OPL language. The second part of the course will pay attention to Constraint-Based Scheduling, which is the discipline that studies how to solve scheduling problems by using CP. Scheduling has been a main area where CP has been successful, and CP is a leading technology to solve scheduling problems. The course will pay extensive attention to modeling and solving real-life scheduling problems, with special attention to the way Constraint-Based Scheduling is used in leading Advanced Planning and Scheduling products. The third part of the course is dedicated to studying how CP problems can be solved. Topics like tree search, local search, and large neighborhood search are discussed and detailed examples are given. We will also go into the relationship between Constraint Programming and Mathematical Programming and discuss in what way scientific and industrial experience shows that many of the most challenging combinatorial problems are best tackled by using a combination of techniques, where Mathematical Programming, Constraint Programming, tree search, and neighborhood search are extensively used.

Objectives

This course pays attention to both the theory behind CP as to modeling and solving of combinatorial optimization problems using CP. Special attention is paid to modeling and solving real-life scheduling problems, which is a particular strong point of CP. After taking the course students are able to:

  • explain the theoretical foundations of CP,
  • model and solve combinatorial optimization problems using CP,
  • use CP to model and solve real-life scheduling problems,
  • combine Mathematical Programming and Constraint Programming in solving combinatorial optimization problems,
  • use IBM ILOG CPLEX Optimization Studio and the OPL modeling language.

Staff involved