Course Details
Name:
Type:
Basic information
Code:
Sector:
Credits:
Term:
Module Ricerca Operativa: 2° semester
Degree(s):
Language:
Teacher(s):
Schedule:
Course Objectives
Module Ottimizzazione Combinatoria: Learn algorithmic techniques for some combinatorial optimization problems. Being able to formulate and solve combinatorial optimization problems using integer linear programming. Understand the complexity of the problems studied.
Module Ricerca Operativa: Introduce the student to the formulation of basic Optimization problems, particularly Linear Optimization problems, and train him/her to the related solution algorithms.
Course Content
Module Ottimizzazione Combinatoria
 Prerequisites: graphs, definitions and basic properties. Elements of computational complexity: classes P, NP; polynomialtime reduction and the class NPcomplete. Examples. Combinatorial optimization problems. Basic definitions. Examples: Transversal (vertexcover), stable set, dominating set, edgecover, (perfect) matching, knapsack, graph colouring (chromatic number and index), shortest path, spanning subgraph etc. Formulation as 01 linear programming.
 Unimodular and totally unimodular matrices. Necessary conditions, sufficient conditions. HoffmannKruskal’s Theorem. Convex hull and ideal formulation of an integer LP. Examples: shortest path, mincost flow, bipartite matching, interval graphs.
 Recursion in CO: paths on directed acyclic graphs (DAG) and dynamic programming. Examples of application: optimal paths in a DAG, 01 Knapsack. [Projection of polyhedra, systems of linear inequalities, FourierVeronese’s Theorem, FourierMotzkin’s Method. Fundamentals of duality theory in LP. The PrimalDual Method. Example of application: Dijkstra’s Algorithm].
 Matroids and the Greedy Algorithm. Definition and characterization of a matroid (Rado’s Theorem). Basics of linear algebra: linear/affine dependenceindependence, bases, uniqueness of representation, Steinitz’s (or exchange) Theorem. Examples: trivial matroid, graphical matroid, partition matroid, vector matroid, [matching matroid]. Matroid representation. [An industrial application]. [Rank function, submodular and supermodular set functions. Rank of a matroid. Support function of a convex set. Submodular polyhedron. Lòvasz’s extension. Matroid polyhedron, matroid intersection, intersection of two submodular polyhedra].
 Guaranteed approximation algorithms for CO. Definitions. Polynomial approximation schemes (PTAS, EPTAS, FPTAS). Examples: TSP: double tree and Christofides; Knapsack 01.
 Matching (perfect/nonperfect, weighted/unweighted, bipartite/nonbipartite). Weak dual inequalities: transversal, stability number, edgecover and matching. The bipartite case: Gallai’s and König’s Theorem. [Bistochastic matrices and perfect bipartite matching. Nonbipartite matching: matching polyhedron, Edmonds’ Theorem].
 Linear relaxation of a (mixed) integer linear program. Implicit enumeration: the BranchandBound Method. Linear bounds, example: integer Knapsack, 01 Knapsack. Dichotomy on a fractional variable. Combinatorial bounds, example: TSP.
 [Separation of an integer polyhedron. Tips on the Ellipsoid Method. Separation and optimization: Finding valid inequalities. Solution of LP with exponentially many variables, example: Mincut, TSP, 01 Knapsack, Stable Set].
Module Ricerca Operativa
 Optimization problems: decision varibles, objectives and constraints; modeling techniques and model classification
 Convex optimization problems; local and global optima
 Geometry of Linear Programming
 The Simplex method
 Duality theory in Linear Programming and its applications
 Dual interpretation of the simplex method and the dual simplex method
Learning Outcomes (Dublin Descriptors)
On successful completion of this course, the student should
Module Ottimizzazione Combinatoria
 Being able to evaluate the general complexity of combinatorial optimization problems. Being able to formulate them as 01 linear programming. Know basic primaldual relations. Know elementary matroid theory, dynamic programming. Have the notion and know the main properties of unimodular matrices. Have basic notions on algorithm and problem complexity. Know standard algorithms for spanning tree, bipartite matching, shortest path. Know heuristics for the TSP and Knapsack. Know general implicit enumeration, LP based algorithms (branchandbound)
 Understand the difference between an “easy” and a “hard” problem. Evaluate the complexity of an algorithm and, for simple cases, of a problem. Be able to recognize whether a matrix is, or is not, totally unimodular. Solve by standard algorithms the spanning tree, bipartite matching, knapsack, optimal path, travelling salesman problem. Formulate combinatorial optimization problems, or binary optimization problems derived from applications, as 01 linear programming.
 Understand when a problem has the shape of a matroid and what is the advantage. Know what is the advantage of a totally unimodular matrix. Decide when it is convenient to use dynamic programming. Realize the limits of heuristics.
 Prove rigorously a simple theorem. Prove or disprove (by counterexample) a simple conjecture. Understand the role played by combinatorial optimization in applications.
 Address submodular set functions, polyhedral combinatorics, advanced integer linear programming.
Module Ricerca Operativa

Acquire the knowledge of Optimization problems and of the mathematical modeling techniques for complex decisions. Acquire the knowledge of some solution algorithms for Linear Programming problems.

Acquire the ability to recognize optimization problems and develop mathematical models of decisionmaking problems. Acquire the ability of computing solutions of linear programming problems

Acquire autonomy in modeling and algorithmic choices for problems related to complex decisionmaking

Be able to hold a conversation and to read texts on topics related to the modeling of decision problems and Linear Programming

Acquire the ability of upgrading flexible knowledge and skills in the field of Optimization and related problems that arise in various areas, such as mathematics, computer science and management science
Prerequisites and Learning Activities
Module Ottimizzazione Combinatoria: Notion on basic algorithms and linear algebra, linear programming
Module Ricerca Operativa: Vector space, scalar product, matrix product, inverse matrix
Teaching Methods
Language: Italian
Module Ottimizzazione Combinatoria: lectures, exercises
Module Ricerca Operativa: teaching lessons
Assessment Methods and Criteria
Module Ottimizzazione Combinatoria: written test, oral test
Module Ricerca Operativa: 1. paper test consisting of various exercises (problem formulation, insights about algebraic or geometric problems properties, problem solution by know algorithms)
2. oral test about theoretical topics; this is accessible only for the students who earned a passing grade at the paper test; NOTE: a sufficient paper test allows the student only for the oral at the same date, but NOT for next dates.
3. A midterm test is also planned: a positive grade to it allows the student to skip the corresponding topics in the final test.
Textbooks
Module Ottimizzazione Combinatoria
 W.J. Cook, W. H. Cunningham, W. R. Pulleyblank, A. Schrijver, Combinatorial Optimization. Wiley. 1997.
 C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity. Dover Books on Computer Science. 1998. http://www.amazon.com/CombinatorialOptimizationAlgorithmsComplexityComputer/dp/0486402584 ISBN13: 9780486402581, price: used from $6.24, new from $11.51
 A. Sassano,, Modelli e Algoritmi della Ricerca Operativa. Franco Angeli Editore.
Module Ricerca Operativa
 Dimitris Bertsimas and John N. Tsitsiklis, Introduction to Linear Optimization. Athena Scientific. 1997.
 Matteo Fischetti, Lezioni di Ricerca Operativa. Progetto Libreria Padova. 1995.
 Antonio Sassano, Modelli e Algoritmi della Ricerca Operativa. Franco Angeli. 1992.
Online Teaching Resources
Homepage:
Homepage:
Teaching material:
Teaching material available on the external website https://www.disim.univaq.it/didattica/content.php?corso=115&pid=88. (Module Ottimizzazione Combinatoria) Teaching material available on the external website http://www.di.univaq.it/~smriglio/teach.htm. (Module Ricerca Operativa)
Recent teaching material
Course page updates
This course page is available (with possible updates) also for the following academic years:Course information last updated on: 24 ottobre 2016, 12:01