Unit OPTIMIZATION METHODS
- Course
- Informatics
- Study-unit Code
- A001975
- Curriculum
- In all curricula
- Teacher
- Ivan Gerace
- Teachers
-
- Ivan Gerace
- Hours
- 42 ore - Ivan Gerace
- CFU
- 6
- Course Regulation
- Coorte 2020
- Offered
- 2021/22
- Learning activities
- Affine/integrativa
- Area
- Attività formative affini o integrative
- Academic discipline
- MAT/08
- Type of study-unit
- Opzionale (Optional)
- Type of learning activities
- Attività formativa monodisciplinare
- Language of instruction
- Italian
- Contents
- Linear programming.
Duality theory.
Simplex algorithm.
Integer Linear Programming. - Reference texts
- Christos H. Papadimitriou, Kenneth Steiglitz "Combinatorial Optimization: Algorithms and Complexity" Dover Publications Inc.
- Educational objectives
- The student should be able to describe, analyze, develop and apply numerical methods for Linear Programming and Integer Linear Programming problems.
- Prerequisites
- Basic Linear Algebra.
Basic Programming principles. - Teaching methods
- Face-to-face.
- Other information
- Optional written tests are provided during the lessons.
- Learning verification modality
- There are two tests to have to overcome in order to pass the exam.
The first is a written test. The purpose of this test is to entice the student in the study of solutions to problems through the application of the techniques studied in the theoretical subjects. This stage is essential in order to understand all the potentiality and purposes of the theory. The test is carried out in the classroom and independently by the student. Some exercises are offered to the student with the relevant score. The test is of unlimited duration and the student is free to consulatere books and notes and use the computer. The test is evaluated by checking the proper performance of the year. The test is passed if you get a rating greater than or equal to 16. Passing this test allows admission to the second examination.
The second test is oral. The purpose of this test is to verify the theoretical competence and mastery of the subject by the student. The test can be sustained at any time after the passing of the first examination and lasts about half an hour. The result of this test will determine the final grade exam.
Both tests can be given in English if the student requests it. - Extended program
- Linear programming. Primal problem and dual problem. Theory of duality.
Primal simplex algorithm. Search for admissible primal bases. Dual simplex algorithm. Search for admissible dual bases.
Complexity classes P and PN. NP-complete and NP-hard problems. Integer Linear Programming. Totally unimodal matrices. Cutting techniques.