ECTS credits ECTS credits: 5
ECTS Hours Rules/Memories Student's work ECTS: 85 Hours of tutorials: 5 Expository Class: 20 Interactive Classroom: 15 Total: 125
Use languages Spanish, Galician
Type: Ordinary subject Master’s Degree RD 1393/2007 - 822/2021
Departments: Statistics, Mathematical Analysis and Optimisation
Areas: Statistics and Operations Research
Center Faculty of Mathematics
Call: First Semester
Teaching: With teaching
Enrolment: Enrollable | 1st year (Yes)
This course aims to familiarize students with linear and integer programming models. The objectives to be achieved as a result of learning are:
• Know how to identify and model complex linear and integer programming problems.
• Know how to identify and model complex network optimization problems.
• Know the appropriate software to solve linear and integer programming problems and optimization in networks.
Lesson 1. Introduction to mathematical optimization (7 hours)
- Classes of optimization problems
- Algorithms and computational complexity
- Practical resolution of optimization problems
- Practical examples with R and lpSolveAPI
- Practical examples with AMPL with and without NEOS
Lesson 2. Linear programming (18 hours)
- Introduction
- Definitions and Examples
- Graphic Resolution of Linear Programming Problems
- Linear Algebra, Convex Analysis and Geometry
- Properties of Linear Programming Problems
- Fundamentals of the Simplex Method
- The Simplex Method
- Duality and Sensitivity Analysis
- Linear Reformulations of non-linear elements (with R and AMPL)
Lesson 3. Integer programming (6 hours)
- Introduction
- Examples of Integer Programming Problems
- Formulating Logical Relations with Binary Variables
- Resolution Techniques: Branch and bound
- Introduction to heuristics (on an example of the traveling salesman problem)
- Applied examples of integer programming problems (with R and AMPL)
Lesson 4. Introduction to network optimization problems (4 hours)
- Basic concepts of graph theory
- Flow problem in networks with minimal cost and unimodularity
- Applied examples of network flow problems (with R and AMPL)
Basic bibliography:
• AHUJA, R.K./ MAGNANTI, T.L./ ORLIN, J.B. (1993): "Network Flows. Theory, Algorithms and Applications". Prentice-Hall (book available in https://dspace.mit.edu/handle/1721.1/49424, MIT, Massachusetts Institute of Technology).
• ANDERSON, D. / SWEENEY, D. / WILLIAMS, T. (1993): “Introducción a los modelos cuantitativos para administración”. Grupo Editorial Iberoamérica.
• BAZARAA, M. / JARVIS, J. / SHERALI, H. (2005): “Linear programming and networks flows”. John Wiley & Sons.
• FOURER, R. / GAY, D. M. / KERNIGHAM, B. W. (2002): “AMPL: A modeling language for Mathematical Programming”. Ed. Duxbury Press.
Acceso online: https://ampl.com/resources/the-ampl-book/chapter-downloads/
• HILLIER, F. / LIEBERMAN, G. (2005): “Introduction to operations research”. McGraw-Hill.
• LUENBERGER, D., YE, Y. (2016): "Linear and nonlinear programming". Springer. Acceso online: https://link.springer.com/book/10.1007%2F978-3-319-18842-3
• MARTÍN, Q. / SANTOS, M. T. / SANTANA, Y. (2005) “Investigación operativa: problemas y ejercicios resueltos”. Pearson.
• VANDERBEI, R. J. (2014): "Linear programming". Springer. Acceso online: https://link.springer.com/content/pdf/10.1007%2F978-1-4614-7630-6
Complementary bibliography:
• AARTS, E. / LENSTRA, J. K. (2003): “Local search in combinatorial optimization”. Ed. Princeton University Press.
• BHATTI, M. A. (2000): “Practical optimization methods”, Springer-Verlag.
• CORTEZ, P. (2014): ``Modern optimization with R”, Springer-Verlag.
• DENARDO, E. V. (1982): “Dynamic Programming. Models and applications”. Ed. Prentice-Hall.
• FERRIS, M. C. / MANGASARIAN, O. L. / WRIGHT, S. J. (2007): “Linear programming with MATLAB”. Ed. MPS-SIAM Series on Optimization.
• GOBERNA, M. / JORNET, V. / PUENTE, R. (2004): “Optimización lineal. Teoría, Métodos y Modelos”. McGraw-Hill.
• JENSEN, P. A. / BARD, J. F. (2003): “Operations research models and methods”. Ed. Wiley.
• MARTÍN, Q. (2003): “Investigación operativa”. Pearson. Hespérides.
• PARLAR, M. (2000): “Interactive operations research with Maple. Methods and models”. Birkhauser.
• RÍOS INSUA, S. / RÍOS INSUA, D. / MATEOS, A. / MARTÍN, J (1997) : “Programación lineal y aplicaciones”. Ra-Ma.
• RÍOS INSUA, S. (1996): “Investigación operativa. Programación lineal y aplicaciones”. Centro de Estudios Ramón Areces.
• SALAZAR GONZÁLEZ, J. S. (2000): “Lecciones de optimización”. Servicio de Publicaciones de la Universidad de la Laguna.
• SALAZAR GONZÁLEZ, J. S. (2001): “Programación Matemática”. Díaz de Santos.
• TAHA, H. (2004): “Investigación de operaciones”. Ed. Pearson.
• THIE, P. R. / KEOUGH, G. E. (2008): “An introduction to linear programming and game theory”. Ed. Wiley.
• WINSTON, W. (2003): “Introduction to mathematical programming: operations research”. Pacific Grove : Brooks/C.
In this subject the basic, general and transversal competences collected in the memory of the title will be worked on. The specific competences that will be promoted in this area are indicated below:
E1 - Know, identify, model, study and solve complex statistical and operational research problems, in a scientific, technological or professional context, arising from real applications.
E2 - Develop autonomy for the practical resolution of complex problems arising in real applications and for the interpretation of results in order to aid decision-making.
E6 - Acquire advanced theoretical-practical knowledge of different mathematical techniques, specifically oriented to aid in decision-making, and develop reflective capacity to evaluate and decide between different perspectives in complex contexts.
E7 - Acquire advanced theoretical-practical knowledge of different mathematical optimization techniques, both in one-person and multi-person contexts, and know how to apply them with sufficient autonomy in a scientific, technological or professional context.
The teaching will consist of expository and interactive classes, as well as the tutoring of the learning and the tasks entrusted to the students.
In the expository and interactive classes, examples will be solved using the R software (https://www.r-project.org/), and the AMPL modeler together with the Gurobi solver on the NEOS server (https: // neos-server. org / neos /) optimization, so it is necessary for students to have a computer in the classroom.
Activities will be proposed for the students, which will consist of solving questions, exercises and examples related to linear and whole programming.
The notes of the subject will be provided, as well as other guide material for learning the software. The notes and other teaching tools will be available through some web access tool.
The final grade will come, 100%, from the continuous evaluation, which will consist of the delivery and review of different works proposed throughout the course, including the possibility that the evaluation is based on the oral presentation of some of the works.
Specifically, the student has to do a job for each of the 4 subjects of the subject. In these works, students will use software such as the R program and the AMPL modeler together with the Gurobi solver on the NEOS optimization server (or using an academic or trial license) and write the conclusions drawn.
From these works, it will be possible to assess the level of acquisition of the basic competences CB6-CB10 (modeling problems, arguing their adequacy against other alternatives) and general CG1-CG5. The level reached in the specific competences E1, E2 and E7 will also be evaluated (problem solving, use of specific algorithms and discussion and presentation of the solutions obtained). Likewise, the level reached in the transversal skills CT1, CT3-CT5 will be taken into account in the evaluation, so that some of the work will be carried out in a group.
Each ECTS credit translates into 7 hours of face-to-face class. It is estimated that the student will need, for each classroom hour, an additional hour for the global understanding of the contents. In addition, the continuous assessment work will amount to 10 hours per ECTS credit. In total 24 hours for ECTS credit will result.
Students should have basic knowledge of algebra, geometry, probability calculus, and statistics. It is also advisable to have average computer skills, and in particular statistical and operational research software. For a better learning of the subject, it is convenient to keep in mind the practical sense of the methods that are being known.
It is recommended to actively participate in the learning process of the subject: attendance and participation in the theoretical, practical and computer classes, use of hours of tutoring and the realization of a responsible effort of work and personal assimilation of the studied methods.
As learning resources, use will be made of the bibliography and notes, free or licensed software, and supporting material provided through the website of the Master in Statistical Techniques.
The development of the contents of the subject will be carried out taking into account that the competences to be acquired by the students must meet the MECES3 level. In this sense, although the subject contents focus on linear and integer programming models, the course will have a large practical component, with an emphasis on the identification and modeling of real problems.
In particular, all phases of the methodology of operational research will be presented: definition of the problem (alternatives, objectives, restrictions and data collection), formulation of a model (selection of decision variables and definition of functions), solution of the model (exact resolution algorithms), model validation, special techniques, approximate solutions, heuristics and meta heuristics (for complex problems) and implementation of the solution. Attention will be paid to the formulation of logical relationships and to the linear reformulation of nonlinear problems and will show applied examples of linear, integer and flow programming in networks taken from the field of economics and engineering.
As a problem solving tool, in addition to working with a specific tool for linear problems (such as LPSolve or Gurobi), some algebraic modeling language (such as AMPL) will be studied. These languages allow rapid modeling and resolution of complex problems.
COVID19. The teaching methodology set out in this teaching guide will be used regardless of the degree of attendance under which the subject is taught. If necessary, the use of the master's video conference room will be replaced by the MS TEAMS platform or a similar one. Likewise, the evaluation method will not need any type of modification, since it consists solely of the delivery of work by the students.
In cases of fraudulent performance of exercises or tests, the provisions of the respective regulations of the universities participating in the Master in Statistical Techniques will apply.
This guide and the criteria and methodologies described therein are subject to modifications arising from regulations and directives of the universities participating in the Master in Statistical Techniques.
Balbina Virginia Casas Mendez
Coordinador/a- Department
- Statistics, Mathematical Analysis and Optimisation
- Area
- Statistics and Operations Research
- Phone
- 881813180
- balbina.casas.mendez [at] usc.es
- Category
- Professor: University Lecturer