| Code |
16612
|
| Year |
3
|
| Semester |
S2
|
| ECTS Credits |
6
|
| Workload |
TP(60H)
|
| Scientific area |
Mathematics
|
|
Entry requirements |
N/A
|
|
Learning outcomes |
It is intended that students complement the knowledge acquired in the Linear Programming course with the study of Integer Linear Programming (ILP) problems. Problems of this nature, in which the variables are integers and/or binary, have high applicability and frequently occur in real life. Furthermore, since many of these problems belong to the NP-difficult class, it is essential to study good formulations for them, as well as to efficiently obtain good quality solutions, which constitute the two main objectives of this curricular unit. More specifically, the objectives are:
1) Distinguish fundamental PLI concepts;
2) Model problems in PLI;
3) Differentiate relaxations from a PLI problem;
4) Distinguish (totally) unimodular matrices;
5) Compare formulations;
6) Determine valid inequalities;
7) Apply the partition and evaluation method;
8) Differentiate and apply heuristics.
|
|
Syllabus |
1. Introduction
1.1) Definitions and fundamental concepts of Integer Linear Programming (ILP)
1.2) Some special cases of PLI
1.3) PLI applications
1.4) Relaxations of a PLI problem
2. Linear Relaxation
2.1) Definitions and preliminary results
2.2) Unimodularity
2.3) Convexification of a PLI problem
2.4) Reformulation of a PLI problem
2.5) Valid inequalities and cutting planes
2.6) Linear duality
3. Branch and Bound Method
3.1) Introduction
3.2) Branch
3.3) Bound
3.4) Strategic issues
3.5) Applications
4. Heuristic Methods
4.1) Introduction and fundamental concepts
4.2) Construction methods
4.3) Adaptive methods
4.4) Improvement methods
4.5) Meta-heuristics
|
|
Main Bibliography |
- Wolsey, L. (1998). Integer Programming. Wiley.
- Beasley, J. (1996). Advances in Linear and Integer Programming. Oxford University Press.
- Lawler, E. (1976, 2011). Combinatorial Optimization: Networks and Matroids. Dover.
- Papadimitriou, C., Steiglitz, K. (1998). Combinatorial optimization: algorithms and complexity. Dover.
|
|
Teaching Methodologies and Assessment Criteria |
The teaching methodology is based on theoretical-practical classes. The theoretical part takes place with a presentation by the teacher, accompanied by examples, and with dialogue with the students, who are provided with notes written by the teacher. The practical part of the classes is based on solving exercises, both accompanied and independently. The assessment carried out throughout the teaching-learning period will consist of two written tests. The student may also take a final exam.
|
|
Language |
Portuguese. Tutorial support is available in English.
|