Learning objectives
Propose a formative path which, starting from the simple analysis of the actual application problems to provide the student with the ability to apply the techniques of modeling and solving mathematical programming problems (in particular, continuous linear programming and Length) to define and identify appropriate solutions the resolution , through the tools of mathematical programming, to create applications that solve them by designing models and appropriate solution techniques.
With reference to the Dublin Indicators:
Knowledge and understanding
The course focuses on the knowledge of fundamental modeling techniques with particular emphasis on the study of appropriate solutions to implement applications and design of solution methods . The reference text is in English, which facilitates access to international scientific literature.
Ability to apply knowledge and understanding
The theoretical knowledge presented is always applied to solving specific problems. The exercises that accompany the course focus on solving exercises and problems. Often the solution methods are presented in an algorithmic form and sometimes also by means of a natural language such as pseudocode, developing in the students the ability to structure procedures useful in numerous for the definition of solution techniques .
Autonomy of judgment
The exercises, which are proposed in relation to the theoretical part carried out in class, can be solved individually or in groups. The comparison with classmates, at work at home or during classroom activities, favors the development of specific skills in order to clarify their arguments to classmates or teachers. Often the proposed exercises can be solved in very different ways and listening to the solutions proposed by others allows you to develop the ability to identify common structures, beyond the apparent superficial differences.
Communication skills
The numerous discussions on the different methods of solving the proposed problems allow you to improve communication skills. Furthermore, some specific communication methods of algorithmic analysis are usually used during the explanations (and explicitly highlighted in class) .
Learning ability
The study of the origins of mathematical solutions and their introduction motivated by quantitative considerations helps to realize in the students the ability to learn in a profound way and not just superficial and repetitive. The knowledge thus acquired is never rigid and definitive, but is perfectly adaptable to any evolution and change of perspective and context.
Prerequisites
Basics of linear algebra and analysis
Course unit content
I. Mathematical Programming
II. Computational Complexity Classes
III. Linear Programming (PL)
IV. Dual of a linear programming problem
V. Integer Linear Programming (PLI)
VI. Formulation and problem solving of PL with AMPL
VII. Flow Problems on Networks and Problems on Graphs
VIII. Solution methods: Exact and non-exact methods.
Full programme
Mathematical programming, application examples.
Definition of Linear and Non Linear Programming
Computational Complexity Classes: class P and its properties; NP class and its properties; NP-hard class and its properties; NP-complete class and its properties; strongly NP-complete class and its properties.
Linear Programming (PL):
Introduction to LP and formulation of an LP problem; Geometry of a continuous LP problem; Simplex Method. Two-Phase Method and Big-M Method.
Dual of a linear programming problem:
Properties of duality; Complementary discards; Dual simplex algorithm; Sensitivity Analysis
Integer Linear Programming (ILP): Introduction to ILP; Linear relaxation; Special ILP problems with unimodular constraint matrix: the Transport Problem, North West corner method and Cycle Rule; the Problem of Assignment;
Formulation and problem solving of PL with AMPL
Flow Problems on Networks and Problems on Graphs: Maximum Flow; Flow at minimal cost; Ford-Fulkerson and Rising Paths; Definition of Cut; Minimum cut; the Vertex Cover Minimum Problem; the Minimum Coverage Tree Problem; Kruskal and Prim algorithm; Minimum Path Problems; Dijkstra's algorithm;
Solution Methods: Exact Methods: Branch & Bound; Column Generation, Cutting Plans, Dynamic Programming; Approximation methods; Heuristic and Metaeuristic methods; the 0/1 Backpack Problem and the Fractional Backpack Problem.
Bibliography
D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008
Teaching methods
The main way of transmitting knowledge is the frontal lesson, during which we try to involve students to bring them to conclusions on their own. There are also exercises to consolidate what was seen in the lessons. There are no laboratory activities but a research project is planned to be carried out at home, possibly together with others.
Assessment methods and criteria
The written exam is composed of exercises and theory questions that affect the final grade in the same way. The oral exam is foreseen only at the request of the student.
The student is also asked to work at home on a project, proposed by the teacher or suggested by the student himself, in which he has to develop all the phases of the operative researcher's work: translation of the real problem into a mathematical model, translation of the model into AMPL language , choice of an appropriate solver, analysis of the solution returned by the solver
and sensitivity of the solution obtained with respect to data perturbations. The work performed must be reported in a report which is then discussed with the teacher.
Other information
- - -
