Aim

The purpose of the course is to present the main concepts and methods of discrete optimization and nonlinear (continuous) optimization, which allow to tackle a wide variety of decision-making problems arising in science, engineering and management. Modeling and application-related aspects are also covered.

After some fundamentals of convex analysis, the course is subdivided into two parts. The first one deals with integer linear programming, that is optimization problems with a linear objective function and linear constraints where some (or all) variables are restricted to take discrete (integer) values. The second part is devoted to nonlinear optimization with continuous variables.

During the computer laboratory sessions, the students will learn how to use the softwares AMPL (with state-of-the-art solvers like CPLEX) and MATLAB to build optimization models and solve mixed integer linear and nonlinear optimization problems.

Detailed program

1. Introduction

Discrete (integer) and nonlinear (continuous) optimization models, local and global optima, some fields of application.

2. Fundamentals of convex analysis

Separating/supporting hyperplanes, main consequences (Farkas Lemma), characterization of convex functions, subgradients.

3. Discrete optimization

- Integer linear programming (ILP) problems and modeling techniques. Examples: matching, location, routing, scheduling, network flows, covering, packing, partitioning,...
- Alternative, strong and ideal formulations.
- "Easy" ILP problems and totally unimodular matrices.
- Linear, surrogate and combinatorial relaxations.
- Lagrangian relaxation: Lagrangian subproblem, dual problem, subgradient method, choice of Lagrangian dual.  Examples: symmetric travelling salesman, facility location and generalized assignment problems.
- Branch-and-Bound method (ILP and combinatorial optimization problems).
- Cutting plane methods: valid inequalities, Chvátal-Gomory procedure, fractional and mixed integer Gomory cuts, facets of polyhedra, strong inequalities (cover inequalities for the binary knapsack problem, clique and odd cycle inequalities for the independent set problem, cut-set inequalities for TSP), separation problem and lifting procedure.
- Branch-and-Cut method.
- Heuristics: greedy, local search and Lagrangian heuristics.

4. Unconstrained nonlinear optimization

- Optimality conditions.
- Line search methods and convergence rate.
- One-dimensional optimization (Wolfe conditions).
- Line search methods: gradient, conjugate directions, Newton and quasi-Newton methods (DFP and BFGS).
- Subgradient method for convex non-smooth optimization functions.

5. Constrained nonlinear optimization

- Necessary optimality conditions: constraint qualification, Karush-Kuhn-Tucker conditions.
- Sufficient optimality conditions: Lagrange function, saddle points, weak and strong duality.
- Methods for quaratic programming problems (null space and active set methods).
- Penalty, barrier and augmented Lagrangian methods.
- Basics of quadratic sequential programming.

Prerequisites

The prerequisites for the course include linear programming (basic feasible solutions, simplex algorithm, duality), graph optimization (minimum spanning tree, shortest paths, maximum flow), and the basics of NP-completeness theory. These topics are covered in the course "Foundations of Operations Research".

Organization

Besides the lectures, the course includes 9 exercise sessions of 90 minutes and 6 computer laboratory sessions of 90 minutes.

Approximately every ten days, the students will be assigned a set of exercises to be solved before the next exercise session.
 

Joint courses: "Ottimizzazione Discreta" and "Complementi di  Ricerca Operativa"

The courses "Ottimizzazione Discreta" and "Complementi di Ricerca Operativa" (5 cfu) correpond to two overlapping parts of the course "Optimization" (8 cfu).

While "Optimization" includes all the material presented during the lectures, the exercise and computer laboratory sessions,

- the course "Ottimizzazione Discreta" (5 cfu) includes the chapters 1-3, the exercise series 1-5 and the computer laboratory sessions 1-3,

- the course "Complementi di R.O." (5 cfu) includes the chapters 1, 2, 4 e 5, the exercise series 1,6-9 and the computer laboratory sessions 4-6.

The students enrolled in both courses "Ottimizzazione Discreta" (5 cfu) and "Complementi di R.O." (5 cfu) must take the written exam of "Optimization" (8 cfu) and conduct a project or an individual study (2 cfu) to be defined with the instructor.

A comprehensive written exam covering all the material presented during the lectures, the exercise sessions and the computer laboratory sessions.

The prerequisite to take the written exam is that the students must have attended and actively participated in at least 5 of the 6 computer laboratory sessions.

The material will be made available during the semester

Third edition