Combinatorial Optimisation

Recommended Prerequisites

Linear Programming and Discrete Mathematics.

Teaching Methods

If a student does not comply with the relevant requirements, than instead of handing out homework and taking mid-term tests he/she must take an exam that represents 90% of the final grade.

Learning Outcomes

In Combinatorial Optimization, we will study combined combinatorial techniques, linear programming and algorithms for solving optimization programs in discrete or mixes structures. Some real problems examples include timing classes and exams in a school, sequencing tasks in an industrial process, dimensioning staff in a service center and dimensioning telecommunication networks. Most problems come from areas such as Operational Research and Computer Sciences.

Generic competences:

Competence in using computational tools;

Knowledge of mathematical results;

Capacity for generalization and abstraction;

Capacity for formulating and solving problems;

Conception or use of mathematical models in real situations;

Rigorous and clear written and spoken expression;

Capacity for research;

Imagination and creativity;

Critical thinking;

Communication skills.

Work Placement(s)

No

Syllabus

Minimum spanning tree (Prim and Kruskal).

Shortest paths (Ford-Bellman and Dijkstra).

Maximum Flux and Minimum Cut (Ford-Fulkerson).

Pairing in bipartite (Kuhn) and non-bipartite (Edmonds) graphs.

Total Unimodality (Hoffman-Kruskal and Ghouila-Houri).

Facial structure of polyhedrons (polar, extreme points, faces, facets).

Cutting planes (Gomory, lift-and-project, split, mir).

A computational study (e.g., the problem of the travelling salesman).

Assessment Methods

Assessment
Presentation of a paper (10%) + Homework and Two mid-term tests (90%) or Exam (90%): 100.0%

Bibliography

COOK, W.; CUNNINGHAM, W.; PULLEYBLANK W. [et.al.] (1998). Combinatorial Optimization, Wiley-Interscience. (Cota na Biblioteca: 90C/Com.Coo)