Learning objectives

The first aim of the course is to offer a motivated
introduction to Linear Programming (LP, simplex method and duality theory), to the use of Integer Linear Programming (ILP, mathematical modelling), and to Combinatorial Optimization (CO, shortest paths, max-flow min-cut theorem, bipartite matching), with the explorations of the links among them.
Our approach will be algorithmic. Basic and fundamental techniques and methodologies for mathematical investigation will be underlined and
rediscovered also taking inspiration from Computational Complexity
theory.

Prerequisites and basic notions

rudiments of analysis, calculus and linear algebra

Program

1. Good characterizations, recursion, and Dynamic Programming (DP)
1.1] tiling problems and puzzles: YES and NO certificates and their role
1.2] good conjectures, their flavour, and how to prove them
1.3] from recursion/induction to dynamic programming
2. Introduction to Linear Programming (LP)
2.1] LP problems and ILP problems, a computational complexity perspective
2.2] the simplex method
2.3] duality theory
2.4] complementary slackness
2.5] economic interpretation
3. Introduction to graphs and Combinatorial Optimization (CO)
3.1] graphs and digraphs as models
3.2] a few good characterizations (connectivity, Eulerian graphs, bipartite graphs, DAGs)
3.3] Bellman-Ford's algorithm. Simple Temporal Networks (STNs) and scheduling

Bibliography

When and where

The meetings will take place in Povo but also be accessible via streaming (for the students in Verona). The commitment on our side is to make the meetings as interactive as possible (also for those students participating from remote).
A Discord server or Telegram group will help not only keep in contact but it will also offer an effective channel for communicating among us.

Learning assessment procedures

Participate actively in the meetings and obtain sufficient scores on the exercises proposed as homework. You can gather in groups for some or all of the exercises (this is actually encouraged so that this first course of our doctoral school can also be an opportunity to get to know each other). However, you are supposed to have a good understanding of each solution you submit under your name.
No deadline is set for you to submit your solutions; everyone can follow their own pace and take their time to carry out the exercises and develop their own solutions. However, try to present at least some or part of the solutions already during the meetings, so as to have the opportunity to discuss them, offer hints, do some troubleshooting, resolve ambiguities or provide missing pieces. Some exercises may require you to write running code (just a few lines, in any language of your choice, e.g., C/C++, Pascal, Python). The programming will not be your problem even if you are new to it (if so, it will be a good occasion to get a first experience or some confidence with it). For these exercises, you will have the opportunity to submit these small codes to our system which will test and assess your solutions and provide you with immediate validation and feedback.
Each problem comes with its own maximum score (usually 100), which you will get in full if your algorithmic solution is topmost smart and efficient (otherwise you will go collecting partial points on more of the exercises). You must collect at least 1000 points in total to pass the exam.

Assessment

The evaluation is binary: after having collected a sufficient score, the student asks me to notify his/her passing of the exam to the respective doctoral school/institution.