Constraint Programming

Constraint Programming

Course
en
English
112 h
This content is rated 0 out of 5
Source
  • From www.edx.org
More info
  • 10 Sequences
  • Advanced Level
  • Starts on August 6, 2024
  • Ends on July 27, 2024

Their employees are learning daily with Edflex

  • Safran
  • Air France
  • TotalEnergies
  • Generali
Learn more

Course details

Syllabus

Module 1: From Backtracking Search to the Constraint Programming Paradigm
Starting from a custom backtracking search algorithm for the N-Queens Problem, we will make the approach gradually more generic until the introduction of a purely declarative approach and the design a first tiny CP library.

Module 2: Introduction to Mini-CP
The design and internals (variables, domains, state restoration, etc.) of Mini-CP, the constraint programming library that is used along the course and that is extended in each assignment.

Module 3: The sum and element global constraints
Two constraints that occur for solving most of the CP problems. Design of their filtering algorithms, study of their properties and implementation.

Module 4: The extensional table constraint
Introduction to the table constraint, the most generic one can imagine in CP. Study of some of its application, and filtering algorithms for this constraint.

Module 5: The alldifferent constraint
Study of the alldifferent global constraint as an illustration of an elegant reuse of well-known graph algorithms embedded into the filtering of constraints.

Module 6: The Circuit constraint and Vehicle Routing Problems (VRP)
Introduction to solving VRP with CP using the successor model and the circuit global constraint. Introduction to solving optimization problems with CP and Large Neighborhood search.

Module 7: Cumulative Scheduling Problems
Introduction to Scheduling with CP and the cumulative constraint, instrumental for scheduling non preemptive tasks with resource requirements.

Module 8: Disjunctive Scheduling Problems
A specific case of scheduling problems is the one of disjunctive resource where activities cannot overlap in time. We will study specific filtering and search techniques and apply it to solve the well kownknown job-shop problem.

Module 9: Blackbox Search
Introduction to efficient search heuristics independent of the problem to solve. All these searches are declinations of the well-known first-fail principle.

Module 10: Modeling
Introduction to advanced modeling techniques to boost the solving of your problems, including redundant constraints, and symmetry breaking.

Prerequisite

A graduate level understanding of data-structures and algorithms.
Be familiar with the Java programming language which used for the programming assignments.

Instructors

Pierre Schaus
Laurent Michel
Pascal Van Hentenryck

Platform

Harvard University, the Massachusetts Institute of Technology, and the University of California, Berkeley, are just some of the schools that you have at your fingertips with EdX. Through massive open online courses (MOOCs) from the world's best universities, you can develop your knowledge in literature, math, history, food and nutrition, and more. These online classes are taught by highly-regarded experts in the field. If you take a class on computer science through Harvard, you may be taught by David J. Malan, a senior lecturer on computer science at Harvard University for the School of Engineering and Applied Sciences. But there's not just one professor - you have access to the entire teaching staff, allowing you to receive feedback on assignments straight from the experts. Pursue a Verified Certificate to document your achievements and use your coursework for job and school applications, promotions, and more. EdX also works with top universities to conduct research, allowing them to learn more about learning. Using their findings, edX is able to provide students with the best and most effective courses, constantly enhancing the student experience.

This content is rated 4.5 out of 5
(no review)

What did you think of this course?

Complete this resource to write a review