This site uses only proprietary and third party technical cookies. By continuing to browse the site you are agreeing to our use of cookies. I agree I want to find out more
Browse the Department site:
Browse the Teaching site:

Programme of Course "Ricerca operativa e Ottimizzazione"

The course is composed by the following modules: "Ottimizzazione Combinatoria"   "Ricerca Operativa"

F0139

Type of course unit:

Bachelor Degree in Computer Science curriculum General: Compulsory

Semester:

Module Ottimizzazione Combinatoria: 2° semester
Module Ricerca Operativa: 2° semester

Number of credits:

Bachelor Degree in Computer Science: 12 (workload 300 hours)

Teachers:

Claudio Arbib (Claudio Arbib univaq it)
Stefano Smriglio (Stefano Smriglio univaq it)

1. 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.

2. Course Contents and learning outcomes (Dublin Descriptors)

Topics of the course include:

Module Ottimizzazione Combinatoria

• Prerequisites: graphs, definitions and basic properties. Elements of computational complexity: classes P, NP; polynomial-time reduction and the class NP-complete. Examples. Combinatorial optimization problems. Basic definitions. Examples: Transversal (vertex-cover), stable set, dominating set, edge-cover, (perfect) matching, knapsack, graph colouring (chromatic number and index), shortest path, spanning subgraph etc. Formulation as 0-1 linear programming.
• Unimodular and totally unimodular matrices. Necessary conditions, sufficient conditions. Hoffmann-Kruskal’s Theorem. Convex hull and ideal formulation of an integer LP. Examples: shortest path, min-cost 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, 0-1 Knapsack. [Projection of polyhedra, systems of linear inequalities, Fourier-Veronese’s Theorem, Fourier-Motzkin’s Method. Fundamentals of duality theory in LP. The Primal-Dual 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 dependence-independence, 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 0-1.
• Matching (perfect/non-perfect, weighted/unweighted, bipartite/non-bipartite). Weak dual inequalities: transversal, stability number, edge-cover and matching. The bipartite case: Gallai’s and König’s Theorem. [Bi-stochastic matrices and perfect bipartite matching. Non-bipartite matching: matching polyhedron, Edmonds’ Theorem].
• Linear relaxation of a (mixed) integer linear program. Implicit enumeration: the Branch-and-Bound Method. Linear bounds, example: integer Knapsack, 0-1 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: Min-cut, TSP, 0-1 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

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 0-1 linear programming. Know basic primal-dual 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 (branch-and-bound)
• 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 0-1 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.

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 decision-making problems. Acquire the ability of computing solutions of linear programming problems

• Acquire autonomy in modeling and algorithmic choices for problems related to complex decision-making

• 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

3. Course Prerequisites

Module Ottimizzazione Combinatoria: Notion on basic algorithms and linear algebra, linear programming
Module Ricerca Operativa: Vector space, scalar product, matrix product, inverse matrix

4. Teaching methods and language

Module Ottimizzazione Combinatoria: lectures, exercises
Module Ricerca Operativa: teaching lessons

Language:Italian

Reference 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.
• 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.

5. Assessment Methods

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 mid-term test is also planned: a positive grade to it allows the student to skip the corresponding topics in the final test.

Course information last updated on: 24 ottobre 2016, 12:01