Operational Research (ETF RIO OI 4870 ) 

General information 

Module title  Operational Research 
Module code  ETF RIO OI 4870 
Study  ETFB 
Department  Computing and Informatics 
Year  1 
Semester  2 
Module type  Mandatory 
ECTS  7 
Hours  70 
Lectures  40 
Exercises  25 
Tutorials  5 
Module goal  Knowledge and skill to be achieved by students 

Course integrates the knowledge acquired in the course "Fundamentals of operational researchâ, introductory theories and algorithmic methodologies improved to solve problems that are present in social and industrial environment, and the aim is to manage and coordinate activities in the optimal way while the available resources are limited. Students will gain abilities (knowledge) to present real cases (situations) where optimization problems are present using models of linear programming, graph theory and numerical simulation. Students will also be able to solve problems using the appropriate optimization algorithm or using the simulation program. 

Syllabus 

1. Discrete systems simulation <br> 1.1. Statistics rehearsal: aleatory variables <br> 1.2. Production of pseudocausal values, inverse transformation method; <br> 1.3. Static and dynamic system description <br> 1.4. Event programming method <br> 1.5. Flux diagrams for simulation problems <br> 2. Linear programming <br> 2.1. General characteristics of convex programming <br> 2.2. Linear programming and simplex algorithm problem rehearsal <br> 2.3. Theory of duality: dual problem, orthogonality conditions <br> 2.4. Dual simplex algorithm <br> 2.5. Primaldual algorithm <br> 3. Integer linear programming <br> 3.1. Unimodularity (uniextremality) <br> 3.2. Linear programming duality <br> 3.3. Gomory's cuttingplane method <br> 3.4. Branchandbound method <br> 3.5. Mixed and binary linear programming <br> 3.6. The ranch problem 01 <br> 3.7. Branchandcut problem <br> 4. Graph problems <br> 4.1. Graph theory rehearsal <br> 4.2. Relations between the minimum path, flow and linear programming <br> 4.3. Unimodularity of incidental matrix <br> 4.4. Hamiltonians (cycles): "countable" algorithm <br> 5. Complexity theory <br> 5.1. P and NP classes; NP complex problems <br> 5.2. Complexity of basic combinatorial optimization problems <br> 5.3. Dynamic programming <br> 5.4. Strong NPcomplexity problems <br> 6. Branch_and_bound algorithms <br> 6.1. Branching scheme <br> 6.2. Relaxations: continuity, lagrangian, surrogate; <br> 6.3. Application in the multiple ranch problem <br> 6.4. Reduction procedure <br> 6.5. Approximate algorithms: experimental analysis, probability, worst case <br> 6.6. Exact and heuristic type algorithms <br> 6.7. Metaheuristic algorithms <br> 

Literature 

Recommended  1. Notes and slides from lectures (See Faculty WEB Site) <br> 2. S. Martello, 'Ricerca Operativa LS', Esculapio (progetto Leonardo), Bologna, 2004. <br> 3. S. Martello, D. Vigo, 'Esercizi di Simulazione Numerica', Esculapio (progetto Leonardo), Bologna, 2001. <br> 4. S. Martello, D. Vigo, 'Esercizi di Ricerca Operativa', Esculapio (progetto Leonardo), Bologna, 2003. <br> 5. C. Papadimitriou, K. Steiglitz, 'Combinatorial Optimization', Prentice Hall, 1982. <br> 6. S. Martello, P. Toth, 'Knapsack Problems: Algorithms and Computer Implementations',Wiley, 1990. <br> 
Additional  
Didactic methods 

Course is structured in lectures, auditorial and laboratory exercises. <br> During the lectures, theoretical problems and algorithmic aspects of the proof given will be discussed. <br> During the exercises, proposed industrial cases with optimization problems are considered and the appropriate mathematical models for numerical simulation are derived. <br> Solutions for mathematical models are found using algorithms given in the lessons. <br> Laboratory practice (free and optional) is performed with the presence of teaching assistants and demonstrators who will acquaint students with application of necessary software packages in a more detailed way. <br> 

Exams 

During the course students will collect points according to the following system: <br>  Attending lectures, exercises and tutorial classes: 10 points, student with more then three absences from lectures, exercises and/or tutorials can not achieve these points; <br>  Home assignments: maximum of 10 points, assuming solving 5 to 10 assignments evenly distributed throughout the semester; <br>  Partial exams: two written partial exams, maximum of 20 points for each positively evaluated partial exam; <br> Student who during the semester achieved less than 20 points must reenroll this course. <br> Student who during the semester achieved 40 or more points will access to final oral exam, the exam consists of discussing the partial exams tasks, home assignments and answers to simple questions related to course topics. <br> Final oral exam provides maximum of 40 points. To achieve a positive final grade, students in this exam must achieve a minimum of 20 points. Students who do not achieve this minimum will access to makeup oral exam. <br> Student who during the semester achieved 20 or more points, and less than 40 points will access to makeup exam. Makeup exam is structured as follows: <br>  Written part structured in the same way as a partial written exam, during which students solve problems in topics they failed on partial exams (achieved less then 10 points), <br>  Oral part structured in the same way as a final oral exam. <br> Only students who, after passing the written part of the makeup exam managed to achieve a total score of 40 or more points, can access to oral makeup exam, where the score consists of points achieved through attending classes, home assignments, passing partial exams and passing the written part of makeup exam. <br> Oral makeup exam provides maximum of 40 points. To achieve a positive final grade, students in this exam must achieve a minimum of 20 points. Students who do not achieve this minimum must reenroll this course. <br> 

Aditional notes 

For laboratory and homework assignments software packages for linear programming and complete linear programming can be used, as well as the language for numerical simulation (eg, SIMSCRIPT II.5). 