Master in Innovation and Research in Informatics (MIRI)

Combinatorial Problem Solving (CPS)

Semester Spring 2026

Lecturer

Enric Rodríguez


Schedule
  • Theory lectures: Mon 12-14 h., room A6201 (every week)
  • Lab lectures: Thu 12-14 h., room A5S113 (not all weeks, only: TBA)
    •

    About the Course

    Structure

    The course consists of three parts, in which different approaches to combinatorial problem solving are covered. Namely:

  • Constraint Programming (CP)
  • Linear Programming (LP)
  • Propositional Satisfiability (SAT)
    •


    Assessment
     
    50% of the final grade corresponds to theory.
    This grade will be obtained by means of a written exam at the end of the course.

    50% of the final grade corresponds to laboratory.
    This grade will be obtained as the mean of three successive projects (one for CP, one for LP, and one for SAT).

    Materials for Theory

    The slides for each of the theory lectures can be found below.


  • Introduction: Combinatorial Problems: slides

    • CP (slides by courtesy of Javier Larrosa)

  • Introduction to Constraint Programming: slides
  • Local consistency: slides
  • Global constraints: slides
  • Search algorithms: slides


    • LP

  • Basics on Linear Programming: slides
  • The Simplex Method: slides
  • The Revised Simplex Method: slides
  • The Dual Simplex Method: slides
  • Mixed Integer Linear Programming: slides
  • The Network Simplex Method: slides

    • SAT

  • Propositional Logic: slides
  • DPLL algorithm: slides
  • Encodings into SAT: slides
  • CDCL SAT solvers: slides
  • Introduction to SMT: slides


    • Materials for Laboratory

    For each laboratory lecture there is a list of guided practical exercises to be solved, which can be found below.

    CP

    In the lectures of CP, the CP solver Gecode will be used (follow the download instructions).
    The following documents are available:
  • Slides on using Gecode for CP (codes shown on the slides are here)
    •
  • Manual
  • Documentation
    •
    The exercises are:
    1. Graph coloring: statement, checker (which you can use to check your solutions), sample of input and its output, instances. 
    2. Queens problem: statement, checker, run script
    3. Latin square completion: statement, checker, run script, sample of input and its output, instances. 


    LP

    In the lectures of LP, the LP solver CPLEX will be used (to download, register here and follow the instructions).
    The following documents are available:

  • Slides on using CPLEX for LP (codes shown on the slides are here)
    •
  • Documentation

    • The exercises are:
    1. Queens problem: statement, checker, run script
    2. Latin square completion: statement, checker, run script, sample of input and its output, instances.

    SAT

    In the lectures of SAT, the SAT solver kissat will be used (follow the download instructions).
    The following documents are available:
  • Slides on using SAT solvers (codes shown on the slides are here)
    •

    The materials for the lectures are here:

    1. Queens problem: statement, checker, run script
    2. Latin square completion: statement, checker, run script, sample of input and its output, instances.

    Projects
  • The projects for CP, LP and SAT consist in modeling and solving a practical problem using each of the three problem solving technologies, respectively.
  • The statement of the projects will be published at Racó.
  • Projects are individual.

    •    

    Important Dates

     * 17/04: deadline project CP
    * 18/05: deadline project LP
    * 17/06: deadline project SAT

    * 19/06: final exam

    Exams of Previous Courses

    mid-term 12-13-Q2
    final 12-13-Q2
    final 13-14-Q2
    final 14-15-Q2
    final 15-16-Q2
    final-16-17-Q2 and solution
    final-17-18-Q2 and solution
    final-18-19-Q2 and solution
    final-19-20-Q2 and solution
    final-20-21-Q2 and solution
    final-21-22-Q2 and solution
    final-22-23-Q2 and solution
    final-23-24-Q2 and solution
    final-24-25-Q2 and solution

    Bibliography
  • Walsh, Tob; Rossi, Francesca; Van Beek, Pete, Handbook of constraint programming, Elsevier.
  • Williams, H. P, Model building in mathematical programming, Wiley & Sons.
  • Maros, István, Computational techniques of the simplex method, Kluwer Academic Publishers.
  • Biere, Armin, Handbook of satisfiability, IOS Press.
  • Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford, Introduction to algorithms, MIT Press.
    •