Modeling and Solving Discrete Optimization Problems

Credits
4.5
Types
  • MAI: Optional
  • MDS: Optional
  • MEI: Optional
  • MIRI: 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

Competences

Generic Technical Competences

Generic

  • CG1 - Capability to plan, design and implement products, processes, services and facilities in all areas of Artificial Intelligence.

    • Technical Competences of each Specialization

    Academic

  • CEA1 - Capability to understand the basic principles of the Multiagent Systems operation main techniques , and to know how to use them in the environment of an intelligent service or system.
  • CEA13 - Capability to understand advanced techniques of Modeling , Reasoning and Problem Solving, and to know how to design, implement and apply these techniques in the development of intelligent applications, services or systems.

    • Transversal Competences

    Reasoning

  • CT6 - Capability to evaluate and analyze on a reasoned and critical way about situations, projects, proposals, reports and scientific-technical surveys. Capability to argue the reasons that explain or justify such situations, proposals, etc..

    • 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