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
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.
Condividi su