91762 - Combinatorial Decision Making and Optimization

Learning outcomes

At the end of the course, the student has an understanding of the most popular methods in operations research and artificial intelligence for modeling and solving complex combinatorial optimization problems such as constraint programming, integer linear programming, SAT and SMT.

Course contents

The first half of the course will introduce several essential operations research results from linear, nonlinear, integer and combinatorial optimization, privileging the width of the covered area over the depth of the introduction. The topics include:

• Lagrange, Farkas and Karush–Kuhn–Tucker
• Gradient descent, Newton and Quasi-Newton methods
• Linear programming, weak and strong duality
• Simplex algorithm, basic feasible solutions, reduced problem and reduced cots
• Integer linear programming

The second half of the course will introduce the fundamental concepts in SAT and Constraint Programming (CP), two general-purpose approaches in artificial intelligence to combinatorial decision making. The topics include:

• Modelling in CP
• Constraint propagation and global constraints
• Constructive tree search algorithms and branching heuristics
• The SAT problem and basic solving techniques (resolution, unit propagation, DPLL)
• Conflict-driven clause learning algorithms
  
• Encodings into SAT
  
• Satisfiability Modulo Theories
  
  

Readings/Bibliography

1. Lecture slides and bibliography of scientific articles provided by the lecturers.
2. M.S. Bazaraa, J.J. Jarvis e H.D. Sherali. Linear programming and network flows. Wiley, 2010
3. L. A. Wolsey. Integer Programming. Wiley, 1998.                  
4. C. H. Papadimitriou and K. Steiglitz. Combinatorial optimization: algorithms and complexity. Dover, 1998.
5. Handbook of Satisfiability. A. Biere, M. Heule, H. van Maaren, T. Walsh (eds), IOS Press, 2009.
6. Handbook of Constraint Programming. F. Rossi, P. van Beek, T. Walsh (eds), Elsevier Science, 2006.

 

Teaching methods

The course combines theoretical foundations with practical modeling and solving of realistic problems. The teaching methods consist of frontal lectures, including practical exercises, and hands-on experience using personal laptops.

Assessment methods

The students’ level of understanding is assessed through a project work. The students will be asked to work on one project for each of the two modules of the course. The lecturers will propose project topics, however the students are encouraged to coordinate with the lecturers on their own project proposals. The final grade will be the average of the grades obtained from the two projects.

Teaching tools

The lectures are given by using slides which will be made available on the IOL platform.

Links to further information

https://iol.unibo.it/?lang=en

Office hours

See the website of Zeynep Kiziltan

See the website of Vittorio Maniezzo