Combinatorial Problem Solving

You are here

Home » Studies » Masters » Master in Innovation and Research in Informatics » Curriculum » Syllabus » Combinatorial Problem Solving
Credits
6
Types
Specialization compulsory (Advanced Computing)
Requirements
This subject has not requirements, but it has got previous capacities
Department
CS
Web
http://www.cs.upc.edu/~erodri/cps.html
Mail
A combinatorial problem consists in, given a finite collection of objects and a set of constraints, finding an object of the collection that satisfies all constraints (and possibly that optimizes some objective function). Combinatorial problems are ubiquitous and have an enourmous practical importance. In this course we will study three different general paradigms for solving combinatorial problems: linear programming, propositional satisfiability and constraint programming. For each of them, we will study the algorithmic foundations, as well as modelling techniques.

Course Syllabus (summary).
Examples of combinatorial problems. General paradigms: Integer Linear Programming, SAT and extensions, Constraint Programming. Modelling techniques and languages.

Teachers

Person in charge

  • Enric Rodriguez Carbonell ( )

Weekly hours

Theory
2
Problems
0
Laboratory
1
Guided learning
0
Autonomous learning
6.4

Competences

Technical Competences of each Specialization

Advanced computing

  • CEE3.2 - Capability to use a wide and varied spectrum of algorithmic resources to solve high difficulty algorithmic problems.
  • CEE3.3 - Capability to understand the computational requirements of problems from non-informatics disciplines and to make significant contributions in multidisciplinary teams that use computing.

Generic Technical Competences

Generic

  • CG1 - Capability to apply the scientific method to study and analyse of phenomena and systems in any area of Computer Science, and in the conception, design and implementation of innovative and original solutions.
  • CG3 - Capacity for mathematical modeling, calculation and experimental designing in technology and companies engineering centers, particularly in research and innovation in all areas of Computer Science.

Transversal Competences

Reasoning

  • CTR6 - Capacity for critical, logical and mathematical reasoning. Capability to solve problems in their area of study. Capacity for abstraction: the capability to create and use models that reflect real situations. Capability to design and implement simple experiments, and analyze and interpret their results. Capacity for analysis, synthesis and evaluation.

Basic

  • CB6 - Ability to apply the acquired knowledge and capacity for solving problems in new or unknown environments within broader (or multidisciplinary) contexts related to their area of study.

Objectives

  1. Modelling problems arising from computer science and other disciplines in the solving paradigms considered in the course: constraint programming, linear integer programming, propositional satisfiability.
    Related competences: CB6, CTR6, CEE3.3, CG1, CG3,
  2. Becoming familiar with state-of-the-art tools for the solving paradigms considered in the course: constraint programming, linear integer programming, propositional satisfiability.
    Related competences: CTR6, CEE3.2, CG3,
  3. Understanding the algorithmic foundations of each of the solving paradigms considered in the course: constraint programming, linear integer programming, propositional satisfiability.
    Related competences: CEE3.2,

Contents

  1. Combinatorial Problems.
    Informal definition. NP-complete problems vs. polynomial-time problems. Some examples and applications: propositional satisfiability, graph coloring, knapsack, bin packing, etc. Approaches to problem solving.
  2. Constraint Programming.
    Basic definitions. Constraint Satisfaction Problems. Examples. Local consistency: arc consistency, directional arc consistency, bounds consistency. Constraint propagation for global constraints: all different. Search algorithms: basic backtracking, forward checking, partial/full lookahead. Variable and value ordering heuristics. Constraint Optimization Problems. Modeling and solving problems with CP.
  3. Linear Programming.
    Review of linear programming: The simplex algorithm. Duality and the dual simplex. Modelling and solving problems with linear programming. Mixed integer linear programming. Branch & bound, cutting planes, branch & cut. Totally unimodular matrices. Network simplex algorithm. Modelling and solving problems with mixed integer linear programming.
  4. SAT solving and extensions.
    Propositional logic. The satisfiability (SAT) problem. DPLL algorithm. Resolution. Conflict-Driven Clause Learning SAT solvers. Modeling and solving problems with SAT: cardinality constraints, pseudo-boolean constraints. Satisfiability Modulo Theories.

Activities

Activity Evaluation act


Introduction to Combinatorial Problems

Introduction to Combinatorial Problems
Objectives: 1 2 3
Contents:
Theory
2h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
0h

Constraint Programming

Modelling and solving with Constraint Programming
Objectives: 1 2 3
Contents:
Theory
8h
Problems
0h
Laboratory
6h
Guided learning
0h
Autonomous learning
12.8h

Linear Programming

Modelling and solving with Linear Programming
  • Theory: Understanding of the materials given in theory sessions.
  • Laboratory: Resolution of the practical exercises of each laboratory session.
  • Autonomous learning: Review and extension of the materials given in theory sessions. Resolution of theoretical exercises.
Objectives: 1 2 3
Contents:
Theory
10h
Problems
0h
Laboratory
4h
Guided learning
0h
Autonomous learning
20.6h

SAT and Extensions

Modelling and solving with SAT and extensions
  • Theory: Understanding of the materials given in theory sessions.
  • Laboratory: Resolution of the practical exercises of each laboratory session.
  • Autonomous learning: Review and extension of the materials given in theory sessions. Resolution of theoretical exercises.
Objectives: 1 2 3
Contents:
Theory
8h
Problems
0h
Laboratory
4h
Guided learning
0h
Autonomous learning
12.8h

Final Exam

The exam covers the topics of modelling and solving with constraint programming, linear programming and propositional satisfiability.
Objectives: 1 2 3
Week: 16
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
19.8h

Practical Work of Constraint Programming

The project consists in modelling and solving a combinatorial problem with constraint programming
Objectives: 1 2 3
Week: 8
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
10h

Practical Work of Linear Programming

The project consists in modelling and solving a combinatorial problem with linear programming
Objectives: 1 2 3
Week: 12
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
10h

Practical Work of SAT

The project consists in modelling and solving a combinatorial problem with SAT
Objectives: 1 2 3
Week: 16
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
10h

Teaching methodology

The main feature of the teaching methodology is the use of materials
accessible through the web, specifically designed for a self-learning
course. These materials allow reformulating teaching in such a way
that the traditional model of classes largely disappears.

Thus:

1. It regards the class as a baseline for work, which the student must
continue and deepen on his/her own.

2. It builds upon high quality materials (slides, lists of problems,
solved problems, examples of laboratory practical work, LP/SAT/CP
software, bibliographic references).

3. It aims at motivating students, with examples, discussions,
comments, etc... The intuitions behind the definitions, properties and
techniques are discussed in group.

The laboratory will encourage independent work by the students. The
role of the teacher will be mainly to assist and evaluate the
students, who should work mostly autonomously.

Evaluation methodology

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, another one for LP, and another one for SAT) that the students will have to hand in.

Bibliography

Basic:

Complementary:

Web links

Previous capacities

Basic knowledge on the Linux operating system and the C++ programming language.
Basic knowledge on linear algebra, graph algorithms and logics.