Modeling and Solving Discrete Optimization Problems

Credits
4.5
Types
Optional
Requirements
This subject has not requirements , but it has got previous capacities
Department
CS
Discrete Optimization Problems appear in a huge number of domains ranging from engineering, logistics, bioinformatics, probabilistic reasoning, resource allocation, scheduling, etc.

In this course we will learn how to identify, model and solve such type of problems. We will use the celebrated declarative approach in which the user models the problem with a generic language and then uses a generic library of solving techniques.

For this course we will use the MiniZinc modeling language and present three solving paradigms that can be used with it: Boolean Satisfiability, Constraint Programming and Integer Linear Programming. For each one we will cover their expressive power and the main intuitions behind their solving techniques.

The course orientation is essentially practical. We will learn mainly through examples, although some theoretical ideas will also be included.

Teachers

Person in charge

  • Francisco Javier Larrosa Bondia (larrosa@cs.upc.edu)

Weekly hours

Theory
1
Problems
1
Laboratory
1
Guided learning
0
Autonomous learning
5.65

Objectives

  1. Ability to model optimally a discrete optimization problem and solve it using the proper tools.
    Related competences: CT6, CEA1, CEA13, CG1,

Contents

  1. Modeling combinatorial problems
    We will use the modeling language MiniZinc to model a wide variety o problems. We will cover topics such as modeling linear problems, sets, functions, and how to deal with symmetries, common sub-expressions, etc
  2. Solving with Constraint Programming
    We will cover issues such as Look-ahead, heuristics, local consistency and global constraints
  3. Solving with Propositional Logic (SAT)
    We will cover topics such as Conjunctive Normal Form (CNF), resolution, unit propagation, clause learning.
  4. Solving with integer linear programming
    We will overview the SIMPLEX algorithm and Branch and Bound

Activities

Activity Evaluation act


Modeling


Objectives: 1
Theory
7h
Problems
7h
Laboratory
7h
Guided learning
0h
Autonomous learning
40h

Constraint Programming


Objectives: 1
Theory
2h
Problems
2h
Laboratory
2h
Guided learning
0h
Autonomous learning
13h

Boolean Satisfiability



Theory
3h
Problems
3h
Laboratory
3h
Guided learning
0h
Autonomous learning
13h

Integer Linear Programming



Theory
1h
Problems
1h
Laboratory
1h
Guided learning
0h
Autonomous learning
7.5h

Teaching methodology

For the modeling part, the "flipped classroom" system will be used where students will have to watch videos and do small projects. Class hours will be used to resolve doubts and consolidate knowledge.

For the part of resolution techniques, the classic master class methodology and some class of problems will be used.

Evaluation methodology

Throughout the course, small projects will be carried out with a combined weight of 20% of the final grade. There will also be a quiz at the beginning of the course, a partial exam and a final exam with a total weight of 80% of the grade

Bibliography

Basic

Web links

  • MiniZinc is a high-level constraint modelling language that allows you to easily express and solve discrete optimisation problems. https://www.minizinc.org/

Previous capacities

Basic Algorithmics