INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION

Obiettivi formativi

Il corso ha per obiettivo quello di fornire agli studenti le nozioni di base di Programmazione Intera e Ottimizzazione Combinatoria. I risultati di apprendimento attesi consistono nella capacità di: 1. riconoscere i problemi di Ottimizzazione Intera e Combinatoria in campo applicativo, sapendone inoltre valutare la complessità e le caratteristiche; 2. effettuare la modellazione matematica dei problemi identificati, scrivendo per essi dei modelli di ottimizzazione; 3. risolvere praticamente i modelli di ottimizzazione individuati, scegliendo opportunamente gli algoritmi e il software di soluzione; 4. sapere interpretare le soluzioni trovate in termini dei problemi applicativi originali. In particolare, facendo riferimento ai Descrittori di Dublino: - Conoscenza e capacità di comprensione: lo studente, al termine del corso, avrà acquisito le conoscenze di base relative ai problemi di Programmazione Intera e Ottimizzazione Combinatoria ed alle relative tecniche di modellazione e soluzione. - Conoscenza e capacità di comprensione applicate: lo studente sarà in grado di riconoscere, modellare e risolvere praticamente i problemi di Ottimizzazione Intera e Combinatoria. - Autonomia di giudizio: lo studente avrà sviluppato la capacità di scegliere opportunamente i modelli, gli algoritmi ed i software di soluzione per risolvere i problemi di Programmazione Intera e Ottimizzazione Combinatoria. - Abilità comunicative: lo studente sarà in grado di comunicare le proprie conoscenze di Programmazione Intera e Ottimizzazione Combinatoria, in particolar modo riguardo alle caratteristiche dei problemi risolti e al significato delle soluzioni trovate. - Capacità di apprendere: lo studente sarà in grado comprendere ulteriori tipologie di modelli, algoritmi e solutori per estendere la propria capacità di risolvere problemi di Ottimizzazione.

Canale 1
ANTONIO MARIA SUDOSO Scheda docente

Programmi - Frequenza - Esami

Programma
Preliminaries of discrete mathematics and algorithms Properties of summations and geometric progressions Induction principle Definition of convex sets and convex functions. Local and global optimums, level line. Quadratic functions and convexity (positive semidefinite matrices) Linear functions, half-spaces and polyhedra. \item Solution of linear systems in two or three unknowns Convex programming, objective function and feasible region. Linear programming Standard and canonical form and graphical solution method. Example of execution of the simplex algorithm. Dictionaries and the revised simplex algorithm. Example of execution of the revised simplex algorithm. Duality theory, strong and weak duality and complementary gaps. Examples of linear programming models. Integer linear programming Notation, properties and linear relaxation Surrogate and Lagrangian relaxations Quality of formulations Logical implications and binary variables \item Examples of integer linear programming models Cutting planes based on Gomory cuts Branch-and-bound algorithm and its properties Branch-and-cut algorithm and its properties Linearization techniques for binary quadratic problems. Piecewise linear functions Computational complexity Sorting and running times of algorithms Knapsack problem Branch-and-bound algorithm for the knapsack problem Dynamic Programming Travelling Salesman Problem
Prerequisiti
Operations Research
Testi di riferimento
- "Introduction to Mathematical Optimization" by Matteo Fischetti - "Linear Programming" by Vasek Chvatal - "Integer Programming" by Michele Conforti, Gérard Cornuéjols, Giacomo Zambelli - "Introduction to Linear Optimization" by Dimitris Bertsimas and John Tsitsiklis.
Frequenza
In presenza
Modalità di esame
Esame scritto
Modalità di erogazione
Frontal teaching
DAVIDE DONATO RUSSO Scheda docente
  • Codice insegnamento10600389
  • Anno accademico2024/2025
  • CorsoIngegneria Gestionale - Management Engineering
  • CurriculumBusiness intelligence and analytics (percorso formativo valido anche ai fini del conseguimento del doppio titolo italo-francese) - in inglese
  • Anno1º anno
  • Semestre2º semestre
  • SSDMAT/09
  • CFU12
  • Ambito disciplinareAttività formative affini o integrative