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
erodri@cs.upc.edu
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

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: CG1, CG3, CEE3.3, CB6, CTR6,
    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: CG3, CEE3.2, CTR6,
    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
    0h

    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
    0h

    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
    0h

    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
    0h

    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.