| 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.
|
|
Teaching Methodologies and Assessment Criteria |
Assessment throughout the teaching-learning period will consist of two in-person assessments (F1, F2). Each assessment will be graded out of 10 points.
The cumulative grade for the tests (N1) is the sum of the two assessments: N1 = F1 + F2
If the cumulative grade is greater than 9.5 (N1 >= 9.5), the student will have to take an oral exam (PO).
The final grade for the teaching-learning period (N) will be the arithmetic mean of the cumulative grade of the tests and the oral exam: N = (N1 + PO) / 2
The minimum grade for admission to the exam is 4 points.
In the exam, all students with a grade greater than or equal to 9.5 will be called for an oral exam graded out of 20 points. The final grade will be the arithmetic mean of the grades from the written exam and the oral exam.
Students with special status have their own rules defined by the academic regulations.
|
|
Language |
Portuguese. Tutorial support is available in English.
|