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.
Person in charge
Enric Rodriguez Carbonell (
Technical Competences of each Specialization
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
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.
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.
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.
Modelling problems arising from computer science and other disciplines in the solving paradigms considered in the course: constraint programming, linear integer programming, propositional satisfiability.
Becoming familiar with state-of-the-art tools for the solving paradigms considered in the course: constraint programming, linear integer programming, propositional satisfiability.
Understanding the algorithmic foundations of each of the solving paradigms considered in the course: constraint programming, linear integer programming, propositional satisfiability.
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.
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.
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.
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.
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.
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.
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.