Linear Programming and Combinatorial Optimization

Year
1
Academic year
2023-2024
Code
02021547
Subject Area
Mathematics
Language of Instruction
Portuguese
Mode of Delivery
Face-to-face
Duration
SEMESTRIAL
ECTS Credits
6.0
Type
Elective
Level
2nd Cycle Studies - Mestrado

Recommended Prerequisites

Knowledge of Linear Algebra and of Discrete Mathematics.

Teaching Methods

Classes of two types: classes where the instructor presents the theoretical concepts and examples, and classes where the students discuss exercises and solve problems. Extensive tutorial time is offered to the students to support the solution of the homework assignments and preparation for the various exams.

Learning Outcomes

Key concepts are defined and classical results of linear programming and combinatorial optimization are demonstrated with an emphasis on common aspects between these two areas. In linear programming, we analyze the simplex algorithm with respect to numerical calculation, convergence, implementation, and post-optimal sensitivity analysis, as well as simplifications resulting from the application to network optimization problems. In combinatorial optimization, one explains the algebraic formulation process and describes algorithms and results for classical problems with and without structure.
The course aims to develop the following skills: knowledge of mathematical results, ability to formulate and solve problems; design and use of mathematical models for real situations. On the personal level it also allows to develop precise and clear oral and written expressions; ability to use computational tools; individual initiative; teamwork; independent learning and independent thinking.

Work Placement(s)

No

Syllabus

Linear Programming
• Linear Program. Feasible basic points. Convexity and extreme points of polyhedra
• Duality. The primal problem and the dual problem. The fundamental theorem of Linear Programming
• Simplex method
• Sensitivity and post-optimal analysis
• Elementary notions of graphs. Minimum spanning tree
• Simplex method for the minimum cost flow problem

Combinatorial Optimization
• Fomulations of linear integer programs
• Shortest path
• Maximum flow / Minimum cut
• Matchings
• Facial structure of polyhedra and cutting plane algorithms
• Study of a specific problem (e.g., travelling salesman).

Head Lecturer(s)

João Luís Cardoso Soares

Assessment Methods

Continuous Assessment
During the semester there are two mid-term exams (75% of the final grade), a set of homework assignments handed in individually (10% of the final grade) and a computational assignment done by a team of 2 or 3 students (15% of the final grade). : 100.0%

Final assessment
The final exam option consists of a single exam (100% of the final grade): 100.0%

Bibliography

W. Cook, W. Cunningham, W. Pulleyblank, A. Schrijver, CombinatorialOptimization, Wiley-Interscience, 1998.

J. Júdice, P. Martins, M. Pascoal, J. Santos, ProgramaçãoLinear, Departamento de Matemática da FCTUC, 2009.

J.J. Júdice, P. Martins, M. Pascoal, J. Santos, OtimizaçãoemRedes, Departamento de Matemática da FCTUC, 2009.

M.S. Bazaraa, J.J. Jarvis, H.D. Sherali, LinearProgrammingandNetworkFlows, segunda edição, Wiley & Sons, 1990.

I. Griva, S.G. Nash, A. Sofer, Linear and Nonlinear Optimization, SIAM, 2009.