Linear Programming and Discrete Mathematics.
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.
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.
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;
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).
Presentation of a paper (10%) + Homework and Two mid-term tests (90%) or Exam (90%): 100.0%
COOK, W.; CUNNINGHAM, W.; PULLEYBLANK W. [et.al.] (1998). Combinatorial Optimization, Wiley-Interscience. (Cota na Biblioteca: 90C/Com.Coo)