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
Esteve Codina Sancho (
)
Others
Albert Solà Vilalta (
)
Joan Garcia Subirana (
)
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
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
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
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
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,
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
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
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
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
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.
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
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
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)
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
Introduction to modeling decisions:
The modeling in the process of decision making. Models of Operations Research. The cycle of operations research methodology
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.
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.
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
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.
Search and evaluation of information for conducting a task in O.R.
Browsers academics. Databases and electronic journals. Assessment Information
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
ActivityEvaluation 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
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
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
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.
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.
Handed a questionnaire completed by the end of the session. This questionnaire will go. Objectives:356472 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:1356472 Week:
8
Theory
2h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
4h
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
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
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
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
Handed a questionnaire completed by the end of the session. This questionnaire will go. Objectives:48910112 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
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
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:134 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:891011 Week:
14
Theory
2h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
4h
Final Exam
It covers all blocs of the subject Objectives:2135647891011 Week:
15 (Outside class hours)
Theory
2h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
6h
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
Pàgina de la Federació Internacional de Societats Professionals d' Investigació Operativa. Es possible mitjançant ella accedir a les pàgines de les Societats Europees, USA etc i les corresponents Societats Nacionals http://ifors.org/web/
Students must have sufficient knowledge of algebra to assimilate the methods exposed algoritmcs should also be able to read English at a technical level