Operational Research (ETF RIO OI 4870 ) |
|
General information |
|
Module title | Operational Research |
Module code | ETF RIO OI 4870 |
Study | ETF-B |
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 pseudo-causal 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. Primal-dual algorithm <br> 3. Integer linear programming <br> 3.1. Unimodularity (uniextremality) <br> 3.2. Linear programming duality <br> 3.3. Gomory's cutting-plane method <br> 3.4. Branch-and-bound method <br> 3.5. Mixed and binary linear programming <br> 3.6. The ranch problem 0-1 <br> 3.7. Branch-and-cut 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 NP-complexity 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 re-enroll 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 re-enroll 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). | |