Portale di Ateneo - En.Unibs.it

Introduction to combinatorial optimization (CO) problems.
Definition of Combinatorial problem. Models, properties and applications
of the OC problems. Alternative formulations for the OC problems.
Strong formulations and linear relaxation. Examples of alternative
formulations for the Minimum Spanning Tree and the Perfect Matching
Problem. Basics of computational complexity theory. Algorithms
classification: exact, heuristic, approximation algorithms.
Polynomial network flows problems
Network flows: basic definitions. Total Unimodularity. Max Flow Problem:
model and properties. Theorem of max-flow min-cut. Ford-Fulkerson's algorithm. Applications. Minimum cost flow problem: properties, solution
algorithms and applications. Minimum cost path problems: properties,
solution algorithms and applications.
Exact Algorithm
Polyhedral theory and algorithms. Branch and Bound method: properties
and drawbacks. Valid inequalities and separation algorithm. Cutting
Planes's algorithm. Gomory's cut and Dantzig's cut. General purpose cuts
and specific cuts: examples. Classes of valid inequalites and exact and
heuristic separation algorithms. Application of the method to the
Traveling Salesman Problem and to an Index Selection Problem. Dynamic
Programming: Bellmann's optimization principle. Problem's
decomposition in stages and states. Recursive optimization. Applications
of the method to the 0-1 Knapsack Problem and to the Minimum path
problem.
Heuristic and meta-heuristic algorithms.
Constructive algorithms and Improvement algorithms. Local Search
algorithms. 2-opt and 3-opt algorithms. Greedy algorithms. Metaheursitic
methods: Tabu Search, Variable Neighborhood Search and
Kernel Search. Main properties of the methods. Application of the
methods to node routing and arc routing problems.
Approximation algorithms
Properties and main features of the approximation algorithms. Worst
case analysis. The tree Algorithm for the traveling salesman problem. A
greedy algorithm for the maximum independent set problem. Next Fit
algorithm for the bin packing problem. Continuos relaxation based
algorithm for the vertex cover problem. greedy algorithms for the 0-1
knapsack problem.