Course Details for A.Y. 2019/2020
Name:
Optimisation Models and Algorithms / Optimisation Models and Algorithms
Basic information
Credits:
: Master Degree in Mathematical Engineering 6 CFU (b)
Degree(s):
Master Degree in Mathematical Engineering 2nd anno curriculum Comune Compulsory
Language:
Italian
![[info]](img/info16.png)
Course Objectives
Be able to: formulate integer linear programming problems, identify major combinatorial optimization problems, distinguish among them according to computational complexity, understand and reproduce main solution methods
Course Content
- Graphs. Finite graphs, vertex and edge set, degrees. Reflexive, non-reflexive, loopless, symmetric, transitive graphs. Regular graphs: examples. Graph isomorphism: examples. Cliques and stable sets. Complement of a graph. Walks, paths, circuits and cycles. Eulerian graphs and Hamiltonian graphs. Making a graph Eulerian. Node degrees and arc set. Odd degrees, Euler Theorem (enunciate). Hamiltonian paths. Connectivity. Trees and forests. Bipartite graphs and their characterization. More optimization problems on graphs: coloring. Applications.
- Combinatorial optimization and 01 LP formulations. Transversal, stable set, dominating set, edge-cover, (perfect) matching in a graph. 01 linear programming formulations. Examples of applications and of formulation. The shortest path problem. Formulation as 01 LP, limits of the formulation. The spanning tree problem. Combinatorial optimization problems in general. Relation to linear programming. Other examples of 01 LP formulation (graph isomorphism problem, PLA folding, maximum cut problem etc.).
- Computational complexity. Complexity of an algorithm, examples. Complexity of a problem, examples. Turing machine. The class P. Polynomial-time reduction. The class NP. The sarisfiability problem. Cook's Theorem (enunciate) and the class NP-complete. Examples of reduction: clique.
- Totally unimodular matrices. The simplex method in a nutshell. LP in general and in standard form, reductions; basis, basic (feasible) solutions. Unimodular and totally unimodular matrices. A sufficient condition for the integrality of basic solutions. Necessary/sufficient conditions for total unimodularity.
- Dynamic Programming. From partial to total order. Topological order of a graph, and DAGs. Bellman condition. Recursive computation of the best path in a DAG. Examples of application (covering a requirement at minimum cost, Levenshtein distance, Knapsack 01 etc.).
- Fundamentals of Duality Theory in LP. Convex polyhedra: algebraic vs. geometric form. Projecting a polyhedron: Fourier-Veronese's Theorem (enunciate). Compatibility of systems of linear inequalities. Fourier-Motzkin elimination algorithm: numerical computation, particular cases. From Fourier-Veronese's Theorem to Duality in LP. Theorems of the Alternative: Gale's Theorem.
- Matching theory. Matching and its relation to edge-cover, transversal and stable set. Gallai's Theorems. Primal-dual relations: Koenig's matching and edge-cover theorems. Bipartite matching and total unimodularity. Augmenting paths and a characterization of max matching. Bipartite matching: algorithms for the unweighted and weighted case. Non bipartite matching: Edmonds' formulation. Bi-stochastic matrices: introduction and definitions. Arithmetical magic squares and their construction. Semi-magic squares and bi-stochastic matrices: Sinkhorn algorithm. Characterization of (extremal) bi-stochastic matrices: perfect bipartite matchings and permutation matrices.
- Matroids and the greedy algorithm. Introduction, motivation, examples. Maximal vs. maximum sets. Cheating the greedy algorithm. Sublclusion and the exchange property:matroids. Characterization of matroids: Rado's Theorem. Examples (uniform matroid, graphical matroid, vector matroid). Matroid representability: vector vs. graphic matroid.
- Approximation algorithms. Introduction to deterministic approximation algorithms. Approximation ratio, polynomial-time approximation schemes. Example 1: TSP. Double tree algorithm. Christofides' (1/2)-approximation algorithm for the metric TSP. Example 2: Knapsack 01. A utility-based dynamic programming algorithm. Complexity. Scaling coefficients: a fully polinomial-time approximation scheme.
- Implicit enumeration algorithms. Search by split. Enumeration tree for COPs. Relations between ILP and LP. Bounds by LP and their use in a branch-and-bound method. First example of a branch-and-bound method: 01-knapsack. Computing the LP bound. Branching on fractional variables. Example: 01 Knapsack. Combinatorial bounds. Example: TSP.
Learning Outcomes (Dublin Descriptors)
On successful completion of this course, the student should
- Know what is a combinatorial optimization problem, and what are the most relevant examples.
Be able to formulate a combinatorial or discrete optimization problem as an integer LP.
Know the main solution methods: the Greedy Algorithm, Dynamic Programming, Branch-and-bound.
Know some special algorithms for special problems.
Distinguish between problem complexities.
Understand the fundamentals of Duality Theory in LP, of Complexity Theory, and of Approximation Theory.
Prerequisites and Learning Activities
Elements of linear algebra
Assessment Methods and Criteria
written test (possibly with midterms), oral test
Textbooks
- Christos H. Papadimitriou, Kenneth Steiglitz, Combinatorial Optimization: Algorithms and Complexity , Prentice Hall (Dover reprint). 1982.
Course page updates
This course page is available (with possible updates) also for the following academic years:
To read the current information on this course, if it is still available, go to the university course catalogue .
Course information last updated on: 25 gennaio 2018, 15:12
Italian version
sad
strutture.univaq