Learning objectives
At the end of the teaching period the student should be familiar with the techniques to model and solve mathematical programming problems (in particular, continuous and integer linear programming, and nonlinear programming). He/she should also be aware of the theoretical results which form the basis for the definition of the solving techniques.
From the practical point of view the student
should be able to build the mathematical model of a real decision problem, individuate the appropriate algorithm (possible applying it through the proposed modeling language), and finally derive and interpret the solution of the model.
Prerequisites
Basic notions of linear algebra and calculus
Course unit content
In the first part of the course mathematical programming problems are introduced and basic concepts for the definition of mathematical programming problems, representing real decision problems, are illustrated. The modeling language AMPL is also introduced as
a powerful tool for a simple use of the most widely employed solvers.
This part requires 12 h.
In the second part Linear Programming (LP) problems are introduced. After the discussion of some theoretical issues, the theory itself is employed for the definition of an algorithmic approach (the simplex algorithm). Duality and sensitivity analysys (e.g., the sensitivity of optimal values and solutions to perturbation of the data) are also discussed.
This part requires 30 h, subdivided as follows:
- PL theory: 6 h
- Simplex algorithm and its variants: 14 h
- Duality: 6 h
- Sensitivity analysis: 4 h
In the third part, Integer Linear Programming (ILP) is introduced. Also here we start with some theoretical issues and then we move to the definition of algorithmic approaches, i.e., cutting plane approaches, branch-and-bound approaches.
This part requires 12 h.
In the fourth and last part of the course we deal with Nonlinear Programming problems. We discuss the theoretical issue of optimality conditions and present the basic components of the main algorithmic approaches.
This part requires 12 h.
Full programme
In the first part of the course mathematical programming problems are introduced and basic concepts for the definition of mathematical programming problems, representing real decision problems, are illustrated. The modeling language AMPL is also introduced as a powerful tool for a simple use of the most widely employed solvers.
In the second part Linear Programming (LP) problems are introduced. After the discussion of some theoretical issues, the theory itself is employed for the definition of an algorithmic approach (the simplex algorithm). Duality and sensitivity analysys (e.g., the sensitivity of optimal values and solutions to perturbation of the data) are also discussed.
In the third part, Integer Linear Programming (ILP) is introduced. Also here we start with some theoretical issues and then we move to the definition of algorithmic approaches, i.e., cutting plane approaches, branch-and-bound approaches.
In the fourth and last part of the course we deal with Nonlinear Programming problems. We discuss the theoretical issue of optimality conditions and present the basic components of the main algorithmic approaches.
Bibliography
Teaching material proposed by the professor and made available online.
Teaching methods
The main way to transmit knowledge is through frontal lessons, during which the students are invited to interact in order to reach by themselves some conclusions.
Exercises are also proposed in order to consolidate what has been seen during the lessons.
Laboratory activities are not present but a project has to be made at home, possibly within a group of two or three people.
Assessment methods and criteria
The written examination is subdivided into two parts which can be given in different moments (it is possible to give the first part during the course). The written exam is made up by exercises and theoretical questions whcih have the same impact on the final mark. The oral examination is only made if required by the student.
It is also required to work at home on a project, proposed by the teacher or by the student, where the student has to go through all the phases of the operations researcher's job: translation of the real problem into a mathematical model, translation of the model into the modeling language AMPL, choice of an appropriate solver, analysis of the final solution and of its sensitivity with respect to perturbation of the data. The work of the student has to be described in a written report, discussed with the teacher. It can be made together with one pr two other students and assigns an additional score ranging from 2 up to 4 points according to its difficulty.
Other information
The teaching material is available at the web site elly.dii.unipr.it
2030 agenda goals for sustainable development
- - -