Operations Research

Credits
6
Types
  • GRAU: Specialization complementary (Computing)
  • GCED: Elective
Requirements
Department
EIO
In the environment of complex organizations of large and medium-range in the industry, government and business, results of decisions that may affect its operation / performance is of utmost importance for the management. Operations Research is a discipline aimed at providing tools for preparation, analysis and efficient resolution of these systems using models which can quantitatively measure the results of the decisions of the leadership of organizations. Today, integration is key for this class of systems to aid decision making within the different information systems that can operate in organizations. The course begins by presenting a case study with which to illustrate these concepts and continues with an exhibition of models established in the Operations Research techniques and their efficient resolution. During the course students develop and solve one of these models adapted to the needs of the real case of an organization and evaluate and discuss their interaction with information systems present in it.

Teachers

Person in charge

Others

Weekly hours

Theory
2
Problems
1
Laboratory
1
Guided learning
0
Autonomous learning
6

Competences

Technical Competences of each Specialization

Information systems specialization

  • CSI2 - To integrate solutions of Information and Communication Technologies, and business processes to satisfy the information needs of the organizations, allowing them to achieve their objectives effectively.
    • CSI2.1 - To demonstrate comprehension and apply the management principles and techniques about quality and technological innovation in the organizations.
    • CSI2.2 - To conceive, deploy, organize and manage computer systems and services, in business or institutional contexts, to improve the business processes; to take responsibility and lead the start-up and the continuous improvement; to evaluate its economic and social impact.
    • CSI2.6 - To demonstrate knowledge and capacity to apply decision support and business intelligence systems.
  • CSI3 - To determine the requirements of the information and communication systems of an organization, taking into account the aspects of security and compliance of the current normative and legislation.
    • CSI3.5 - To propose and coordinate changes to improve the operation of the systems and the applications.
  • CSI1 - To demonstrate comprehension and apply the principles and practices of the organization, in a way that they could link the technical and management communities of an organization, and participate actively in the user training.

    • Computer science specialization

  • CCO1 - To have an in-depth knowledge about the fundamental principles and computations models and be able to apply them to interpret, select, value, model and create new concepts, theories, uses and technological developments, related to informatics.
    • CCO1.3 - To define, evaluate and select platforms to develop and produce hardware and software for developing computer applications and services of different complexities.
  • CCO2 - To develop effectively and efficiently the adequate algorithms and software to solve complex computation problems.
    • CCO2.4 - To demonstrate knowledge and develop techniques about computational learning; to design and implement applications and system that use them, including these ones dedicated to the automatic extraction of information and knowledge from large data volumes.

    • Transversal Competences

    Appropiate attitude towards work

  • G8 [Avaluable] - To have motivation to be professional and to face new challenges, have a width vision of the possibilities of the career in the field of informatics engineering. To feel motivated for the quality and the continuous improvement, and behave rigorously in the professional development. Capacity to adapt oneself to organizational or technological changes. Capacity to work in situations with information shortage and/or time and/or resources restrictions.
    • G8.3 - To be motivated for the professional development, to face new challenges and the continuous improvement. To have capacity to work in situations with a lack of information.

    • Information literacy

  • G6 [Avaluable] - To manage the acquisition, structuring, analysis and visualization of data and information of the field of the informatics engineering, and value in a critical way the results of this management.
    • G6.3 - To plan and use the necessary information for an academic essay (for example, the final project of the grade) using critical reflection about the used information resources. To manage information in a competent, independent and autonomous way. To evaluate the found information and identify its deficiencies.

    • Objectives

    1. Knowing the basic methodology and scope of Operations Research
      Related competences: CSI1, G8.3,
      Subcompetences
      • Distinguish different stages in a project which consists of Operations Research
      • Role of Operations Research models within decision support systems
      • Role of data collection and processing of the necessary information to formulate a model of Operational Research
    2. Learn simple models of O.R., and special solutions
      Related competences: CCO2.4, CSI3.5, G8.3,
      Subcompetences
      • Learn simple models of linear programming: problems of production and mixtures
      • Knowledge of simple models in nonlinear programming: problem of the maximum volume of a cylinder.
      • Learn simple models of integer linear programming: knapsack problem and fixed charge problems
    3. Understand and identify the components of an optimization problem
      Related competences: CCO1.3, CCO2.4,
      Subcompetences
      • Distinguish between decision variables and parameters of an optimization problem
      • Knowing how to use algebraic languages for the representation of optimization problems for the definition and resolution models based on optimization
      • Knowing the central role of an optimization problem as a tool in decision-making processes
    4. Identification of objectives in a decision process. Learn how to express constraints, both linear and nonlinear, to meet the conditions for decision variables in the model. To formulate multiobjective programming models and goal programming models.
      Related competences: CSI2.6, CSI1, CSI2.1,
      Subcompetences
      • Formulation of linear and nonlinear constraints in a model
      • Identify the multiple objectives that may be involved in a model of decision making and its relationship to linear programming models
      • Identification of decision variables and model parameters
      • For problems with two objectives, namely to determine the Pareto optimality frontier
      • Understand and interpret the results and information provided by a model with multiple objectives
      • Knowing the basic formulation of multi-objective problem
      • Being able to define linear programming models suitable for a decision support system and translate them using algebraic manipulation languages,
    5. Understanding the structure and properties of linear and non-linear programming problems
      Related competences: CCO2.4, CSI1,
      Subcompetences
      • Know the distinguishing characteristics of the problems with nonlinearities
      • To know simple linear programming models: the problem of production, the mixing problem
      • Use of Languages ​​manipualció algebraic and spreadsheet. Identify types of solutions provided by algebraic manipulation languages ​​for linear programming problems
      • Know the difference between local and global optimum
      • Knowing the shape of a standard linear programming problem. Slack and excess variables
      • Know how to calculate the basic feasible solutions of a linear programming problem
      • To know the types of solutions that can have a linear programming problem: unique solutions, alternative solutions, infeasible problems, unbounded problems
    6. Understand and apply the simplex method to solve linear programming problems
      Related competences: CCO2.4,
      Subcompetences
      • Purpose of reduced costs . Recognize a basic solution as optimal solution of a problem of linear programming. Recognize when there are alternative optimal
      • Make iterations of the simplex method. Concept base change. Calculating reduced costs
      • Concept of Basis. Understand and distinguish between basic and non-basic variables
    7. Know how to solve linear programming problems in which variables are associated to a graph. networks flow problems.
      Related competences: CCO2.4, CSI2.2,
      Subcompetences
      • Knowing the structure of basic solutions of flow problems on networks. Costs associated with the nodes of trees and dual variables. Calculation of reduced cost coefficients. Cases of one or more items.
      • Application of minimal paths algorithms. (Dijkstra algorithm and labels correcting algorithms)
      • To know the formulation of flow problems in bipartite graphs. Knowing the formulation of the problem at minimal cost.
      • Understand the role of link-node incidence matrix
      • Flow problems on networks with capacities to associate arches. Max Flow min Cut theorem
    8. Understand and apply basic techniques for solving linear problems with integer variables
      Related competences: CCO1.3, CCO2.4,
      Subcompetences
      • Know and be able to apply the algorithm of Branch and Bound
      • Learn the basic models of coating in the form of integer linear programming problem
      • Learn to formulate policies as logical constraints in integer linear programming model
    9. Understand and identify the inputs and outputs of Operations Research models underlying various information systems and decision support systems described in the practical sessions.
      Related competences: G6.3, CCO1.3, CSI1, CSI2.2, CSI3.5,
      Subcompetences
      • Knowing the properties of the Operational Research models seen in the practical sessions.
      • Given a set of requirements of an organization, to examine whether patterns seen in the Operations Research sessions are sufficient to meet these needs. Identify gaps and absences in the modeling.
      • Given certain requirements of an organization in relation to a decision support system, adapt and / or extend the Operations Research models seen in the sessions to meet the requirements.
    10. Being able to apply heuristic methods for integer linear programming problems
      Related competences: CSI2.6, CCO1.3, CCO2.4,
      Subcompetences
      • Apply exchange heuristics for the traveling salesman problem
      • Apply heuristics for plant location problems
    11. Know and be able to apply different kinds of metaheuristics seen in the course
      Related competences: CSI2.6, CCO1.3, CCO2.4,
      Subcompetences
      • Knowing how to apply the technique of simulated annealing to solve routing problems
      • Learn applying taboo search technique to solve integer linear programming
    12. Being able to effectively use information resources in O.R.
      Related competences: G6.3,
      Subcompetences
      • Learn to recognize and use appropriate information to perform a job
      • Knowing the type of information that a source can provide
      • Analysis and synthesis of a particular source of information and value in relation to achieving a goal (realization of a work task or project)
    13. Having proper attitude and motivation towards work
      Related competences: G8.3,
      Subcompetences
      • Motivation for liability, the quality of one's own work and professional realization
      • Adapting to the lack of information and material and temporal constraints
      • Ability to adapt to organizational changes, technology and teamwork

    Contents

    1. Introduction to modeling decisions:
      The modeling in the process of decision making. Models of Operations Research. The cycle of operations research methodology
    2. Continuous programming. Properties and methods
      Characteristics of optimization problems. Formulation of optimization problems. Techniques of mathematical programming. Formulation of problem PL. Troubleshooting PL. The geometry of the PL. The simplex method: basic feasible solutions and extreme points. Sensitivity analysis. Introduction to the presence of nonlinearities in the models.
    3. Continuous programming models and systems to support decision making
      Examples of LP problems: production planning; investment problem, transportation problems, mixture problems, inventory problems. Network flow problems. Multi-objective problems. Programming objectives. Presence of non-linearities in models.
    4. Integer Linear Programming
      Integer Linear programming problem properties. Some problems ple: the problem of scheduling workers, problems with routing problems fixed cost and location algorithms PLE: secant planes; Branch & Bound algorithm
    5. Heuristic methods for solving ILP problems
      Constructive heuristics: Greedy methods. Local search. Metaheuristics: beyond local optima. The method of simulated annealing. Tabu search. Genetic algorithms. Aplications of heuristics to routing and other problems.
    6. Search and evaluation of information for conducting a task in O.R.
      Browsers academics. Databases and electronic journals. Assessment Information
    7. Motivation and attitude to work in O.R.
      Motivation for liability, the quality of their work and professional realization. Ability to adapt to organizational changes, technological. Teamwork. Adapting the lack of information and material limitations and time

    Activities

    Activity Evaluation act


    Block 1. Presentation of the objectives of the basic models of IO and IO

    Monitoring of exposures and review the material proprocionat for the corresponding session. Assimilation of the role of optimization problems as a source of modeling.
    • Theory: Understanding the objectives of the Operational Research as discipline. Understanding the stages of formulation of a methodological model. Validation of a model. Presentation of a case study. Description and analysis of several case studies involved
    • Autonomous learning: Reading and study material prior to the sessions of theory
    Objectives: 1 3 2
    Contents:
    Theory
    1h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    1h

    Analysis of information sources

    Analysis and evaluation of information provided by certain references (software packages / references that can provide solutions to coursework.
    • Theory: Assessment of value and lack of information sel.leccionada.
    • Autonomous learning: Identification of value and information gaps towards the end of the course work
    Objectives: 12
    Contents:
    Theory
    0.5h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    6h

    Block 2. Continuous optimization models and systems to aid decision making

    Follow the models exhibited in the theory sessions. Resolution of monitored and modeling exercises. In the lab sessions, training in the use of algebraic representation languages.
    • Theory: Description of linear programming models and presence of nonlinearities. Exhibition of the principle of Pareto optimality. Minimization of the norm L1. Exhibition of the program objectives and the worst possible case
    • Problems: Formulation of problems and modeling case study
    • Autonomous learning: Reading and study material prior to meetings of theory. Preparation and reading material for laboratory exercises
    Objectives: 1 3 4
    Contents:
    Theory
    4h
    Problems
    2h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    6h

    Using search engines referrals, BD and Electronic

    Search for publications of certain writers in relation to coursework. Viewing videos http://bibliotecnica.upc.edu/habilitats/eines-de-cerca-dinformacio http://bibliotecnica.upc.edu/habilitats/l039estrategia-de-cerca # 4
    • Theory: We provide certain authors and topics related to Employment Course
    • Autonomous learning: Using search engines and initial analysis of references
    Objectives: 12
    Contents:
    Theory
    0.5h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    4h

    Evaluation of the search for references in relation to course work

    Delivery report with the 5 most significant references and details of the search tools used to find them
    Objectives: 12
    Week: 4
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Block 3. Continuous programming problems

    Tracking theory classes with the support of teaching materials produced specifically. Assimilation of basic concepts feasible optimal basis, optimal local and global. Ability to perform the steps of the simplex algorithm. Individual and monitored resolution of problems. Ability to define linear and non linear models using algebraic lenguages in the lab sessions
    • Theory: Characterization of linear programming problems. Basic properties of linear programming problems. The concept of feasible region. Optimal unique alternative. Concept vertex of a polyhedral region. Examples. Bases and basic solutions of the simplex algorithm. Development sessions of basic algebraic theory formulation. Examples of iterations of the simplex algorithm. Method of artificial variables. Presence of nonlinearities. Characteristics of the solutions.
    • Problems: Troubleshooting graphically in two dimensions. Iterations of the simplex algorithm. Troubleshooting with simple algebraic language and concepts to advance laboratory classes
    • Autonomous learning: Work by students with educational material and collection problems. Preparation of lab sessions. Exercises by its own.
    Objectives: 5 6
    Contents:
    Theory
    5h
    Problems
    3h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    8h

    Attitude and motivation toward work. A1

    Students discuss laboratory exercises delivered according to guidelines contained in a section.
    • Laboratory: Quality assessment exercises
    • Autonomous learning: Preparation and adoption by the student
    Objectives: 13
    Contents:
    Theory
    0h
    Problems
    0h
    Laboratory
    1h
    Guided learning
    0h
    Autonomous learning
    3h

    Evaluation of information sources

    Delivery of a report of the evaluation
    Objectives: 12
    Week: 6
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Assessing motivation and attitude towards work. A1

    Using rubrics
    Objectives: 13
    Week: 7
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Block 4. Network Flow Problems

    Make simplex iterations for the problem of min-cost. application of minimal paths algorithms. implementation of the max-flow algorithm min.cut
    • Theory: Exhibition of the min-cost model. Application of the simplex algorithm. Exhibition and derivation of minimal paths algorithms. Illustration of theorem max-flow min-cut
    • Problems: Exercises and tests monitoring methods and algorithms exposed
    • Autonomous learning: Review of material presented in classes of theory test preparation and monitoring. Exercise has to own.
    Objectives: 1 7
    Contents:
    Theory
    3h
    Problems
    4h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    8h

    Evaluation of a lab 1

    Handed a questionnaire completed by the end of the session. This questionnaire will go.
    Objectives: 3 5 6 4 7 2
    Week: 8
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Part 1

    Test problems for units of 1,2,3 and 4 of the course and the corresponding block 8-related objectives associated blocks 1,2,3 and 4.
    Objectives: 1 3 5 6 4 7 2
    Week: 8
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Block 5. Integer linear programming modeling

    Acquire the ability to model using binary variables of type logical conditions. Taking as reference the models presented in the theory sessions in order to undertake their own development and modeling
    • Theory: Exhibition of models covering and partition of sets and the methodology to reflect condition of type logical with integer variables. Exhibition of the fixed charge models.
    • Problems: Modelling of problems with integer variables / binaries inside a collection of problems
    • Laboratory: Formulation, implementation and resolution of a model previously specified in a script lab and variants proposed. Analysis of results
    • Autonomous learning: Reading and studying the material presented in the theory sessions. Resolution individual fitness modeling. Solving the models using algebraic modeling languages. Preparation and reading material for the lab sessions
    Objectives: 1 9
    Contents:
    Theory
    2h
    Problems
    2h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    8h

    Attitude and motivation toward work. A2

    Analysis of the changes proposed by the teacher at Work Course and proposed changes to be made in a limited time. Discussion with other working groups of the adequacy of the solutions adopted
    • Laboratory: Collaborative learning session
    • Autonomous learning: Analysis of proposed changes in the teacher work year. Preparation prior to the meeting
    Objectives: 13
    Contents:
    Theory
    0h
    Problems
    0h
    Laboratory
    2h
    Guided learning
    0h
    Autonomous learning
    5h

    Assessing motivation and attitude towards work. A2

    Delivery of final report to the collaborative session parenentatge
    Objectives: 13
    Week: 11
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Block 6. Integer Linear Programming Problems

    Assimilation of the concepts of branching and quoting. Make iterations of the Branch and Bound algorithm with small problems.
    • Theory: Exhibition programaciói basic properties of linear integer problems and the concept of linear relaxation. Illustration of operation of the branch and bound algorithm.
    • Problems: Resolution of small integer linear programming problems.
    • Autonomous learning: Reading and study material for theory sessions. Preparation exercises for class of problems
    Objectives: 8
    Contents:
    Theory
    2h
    Problems
    2h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    4h

    Attitude and motivation toward work. A3

    Oral presentation of course work in a limited time (10min to the working group)
    • Laboratory: Presentation of course work and discussion
    • Autonomous learning: Preparation for the student
    Objectives: 13
    Contents:
    Theory
    0h
    Problems
    0h
    Laboratory
    2h
    Guided learning
    0h
    Autonomous learning
    5h

    Assessing motivation and attitude towards work. A3

    Oral presentation
    Objectives: 13
    Week: 12
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Block 7. Heuristic methods for integer linear programming problems. Metaheuristics

    Understand the main principles of construction heuristic solutions. Learn to build algorithms based on metaheuristics described. Simulated annealing method, tabu search, greedy search.
    • Theory: Heuristic methods for plant location problems and traveling salesman. Methods of exchange. Construction of solutions. Christofides heuristics. Method of simulated annealing. Taboo Search, Greedy Search
    • Problems: Resolving cases of small hand, applying the heuristics views.
    • Autonomous learning: Monitoring of the exposed material and preparation of material for the lab sessions
    Objectives: 9
    Contents:
    Theory
    4h
    Problems
    2h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    6h

    Evaluation of lab 2

    Handed a questionnaire completed by the end of the session. This questionnaire will go.
    Objectives: 4 8 9 10 11 2
    Week: 13
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Laboratory 1 and 2

    Reading the previous questionnaire and preparation of practice. Execution of the exercise and delivery of completed questionnaire
    • Laboratory: Making classroom practice sessions on PCs. Using algebraic modeling language representation. Resolution and analysis solutions Construction of a metaheuristic algorithm based on a procedure seen in class
    • Guided learning: Development of practice under supervision
    • Autonomous learning: Preparation for student
    Objectives: 3 5 6 7 8 10
    Contents:
    Theory
    0h
    Problems
    0h
    Laboratory
    4h
    Guided learning
    0h
    Autonomous learning
    4h

    Block 8. Course work.

    Assimilating the different stages of formulation, analysis and testing of an optimization model as part of a system to support decision making. Analysis of performance and computational tools used in the performance of the developed model. Development of skills associated to this subject. Students will make up work groups (2 students)
    • Theory: Sessions support and clarification of concepts needed for the tasks of formulating and solving a case study. Development of generic skills associated with the subject.
    • Laboratory: Sessions for the implementation of the formulations of the models. Development of generic skills of the subject.
    • Autonomous learning: Preparation of material. Study and analysis of a small case study. Study and reinforcing concepts displayed the contents of the course
    Objectives: 1 3 4 7 9 10 11
    Contents:
    Theory
    2h
    Problems
    0h
    Laboratory
    6h
    Guided learning
    0h
    Autonomous learning
    8h

    Assessment Course work

    A model will be proposed to the students for its developement along the course. Specific lab sessions will be used for monitoring this activity. Specific objectives: - Development of a model based on optimization problems as part of a system to aid decision making. - Analyze the performance of the computational model developed for use in the environment of proper systems to aid decision making
    Objectives: 1 3 4
    Week: 14
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Part 2

    It consists of test problems for blocks 5,6 and 7 of the subject and the corresponding block 8 related blocks 5.6 and 7.
    Objectives: 8 9 10 11
    Week: 14
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Final Exam

    It covers all blocs of the subject
    Objectives: 2 1 3 5 6 4 7 8 9 10 11
    Week: 15 (Outside class hours)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Teaching methodology

    Learning is done following the methodology of cases, from problems in the area of ​​Operations Research. From these problems will develop the knowledge necessary formal theory classes, classroom and exhibition, and its application in laboratory classes, so that will strengthen the assimilation of various concepts. Used software available on the UPC (AMPL,OPL/Studio Excel).

    Evaluation methodology

    See Addenda for the academic year 2020-21

    NT = Mark for Theory
    NL = Mark for Laboratory sessions. This mark will consist of the marks obtained in the two lab exercises, each one of them weighting 50% of NL
    NTC = Mark for Laboratory Labour Course
    NC = Mark for skills

    N= 0.45*NT + 0.2*NL + 0.25 * NTC + 0.1*NC

    If 0.5* NExP1 + 0.5*NExP2 > = 5 then no need to submit the final exam

    NT = Max (NExF, 0.5 * NExP1 + 0.5N*ExP2)

    NExF Note of the final exam,

    NExP1, NExP2 Notes of partial exams 1 and 2.

    Mark NC will depend on the degree reached at the skills assigned to the subject and the mark will be an average of the marks obtained at each of the skills. (There are two skills, C1, C2. Then
    mark NC will obtained as NC = 0.5*NC1 + 0.5*NC2

    For a given skill i there is the following matching between the level obtained at that skill and the mark NC1, NC2 involved in the final mark

    A level A is equivalent to a mark NC1 (or NC2) that will be between 8,5 and 10
    A level B is equivalent to a mark NC1 (or NC2) that will be between 6.5 and <8,5
    A level C is equivalent to a mark NC1 (or NC2) that will be between 5 and < 6.5
    A level D is equivalent to a mark NC1 (or NC2) that will be between 0 and <5

    Marks for skills are obtained through activities carried out in bloc 8 (Laboratory Labour Course) and Lab sessions.

    Marks NC1, NC2 for skills assigned to this subject will obey to the following expression:

    NCi = 0.25 * NTC + 0.10*NL + Specific Activities for the skill; i=1,2

    Bibliography

    Basic

    Complementary

    Web links

    Previous capacities

    Students must have sufficient knowledge of algebra to assimilate the methods exposed algoritmcs should also be able to read English at a technical level