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: External department linked to the degrees, Statistics, Mathematical Analysis and Optimisation
Areas: Área externa M.U en Técnicas Estatísticas (2ªed), 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. Linear programming (21 hours)
- Introduction.
- Definitions and examples.
- Graphic resolution of linear programming problems.
- Practical resolution of programming problems.
- Practical examples with the appropriate software in optimization.
- 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 appropriate software)
Lesson 2. Overview of mathematical optimization (4 hours)
- Classes of optimization problems.
- Algorithms and computational complexity.
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 appropriate software).
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 appropriate software).
Basic bibliography:
• AHUJA, R.K., MAGNANTI, T.L., ORLIN, J.B. (1993): "Network flows. Theory, algorithms and applications". Prentice-Hall.
• 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.
• HILLIER, F., LIEBERMAN, G. (2005): "Introduction to operations research". McGrawHill.
• LUENBERGER, D., YE, Y. (2021): "Linear and nonlinear programming". Springer. Online: https://link.springer.com/book/10.1007/978-3-030-85450-8
• MARTÍN, Q., SANTOS, M. T., SANTANA, Y. (2005): "Investigación operativa: problemas y ejercicios resueltos". Pearson.
• VANDERBEI, R. J. (2014): "Linear programming". Springer. 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.
• FOURER, R., GAY, D. M., KERNIGHAM, B. W. (2002): "AMPL: A modeling language for mathematical programming". Ed. Duxbury Press. Online: https://ampl.com/resources/the-ampl-book/chapter-downloads/
• GOBERNA, M., JORNET, V., PUENTE, R. (2004): "Optimización lineal. Teoría, métodos y modelos". McGraw-Hill.
• GUROBI OPTIMIZATION. "The Fastest Solver". https://www.gurobi.com/
• 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 appropriate software in 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 and of the peer review of the submitted work. In these works, students will use appropriate software in optimization 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.
However, if the subject is not passed by means of continuous assessment, the student will have two opportunities to take a written exam.
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.
In cases of fraudulent performance of exercises or tests, the provisions of the respective regulations of the participating universities in the Master in Statistical Techniques will apply.
Alejandro Saavedra Nieves
Coordinador/a- Department
- Statistics, Mathematical Analysis and Optimisation
- Area
- Statistics and Operations Research
- alejandro.saavedra.nieves [at] usc.es
- Category
- Professor: LOU (Organic Law for Universities) PhD Assistant Professor