Combinatorial Optimisation
0
2017-2018
01001401
Área Científica do Menor
Portuguese
Face-to-face
SEMESTRIAL
6.0
Elective
1st Cycle Studies
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)
NoSyllabus
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)