| Code |
16611
|
| Year |
2
|
| 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.
|
|
Language |
Portuguese. Tutorial support is available in English.
|