Course Unit Code | 460-4108/01 |
---|
Number of ECTS Credits Allocated | 4 ECTS credits |
---|
Type of Course Unit * | Choice-compulsory type B |
---|
Level of Course Unit * | Second Cycle |
---|
Year of Study * | Second Year |
---|
Semester when the Course Unit is delivered | Winter Semester |
---|
Mode of Delivery | Face-to-face |
---|
Language of Instruction | Czech |
---|
Prerequisites and Co-Requisites | |
---|
| Prerequisities | Course Unit Code | Course Unit Title |
---|
| 460-4062 | Operational Research I |
Name of Lecturer(s) | Personal ID | Name |
---|
| KRO080 | prof. Ing. Pavel Krömer, Ph.D. |
Summary |
---|
The course focuses on advanced topics and methods from the area of operations research. It briefly summarizes the fundamentals of operations research and typical problems solved in this domain. It sums up the simplex algorithm, linear programming, problems with bound variables, and multiobjective problems. Next, it focuses on integer programming, which is an important method for assignment problems. The branch and bound algorithm, the cutting plane method, and network models for integer programming are discussed. Finally, the applications of bio-inspired and stochastic methods (evolutionary computation, swarm intelligence) in operations research with the focus on transportation and assignment problems are presented. |
Learning Outcomes of the Course Unit |
---|
The course will teach advanced techniques of Operations Research. These lectures will extend on the basis of the simplex algorithm with the application of bonded variables and revised simplex algorithm for faster execution. Thereafter, Goal programming will outlines the application of multiple objectives formulation in linear programming. Integer programming, an extension of linear programming will be discussed, where all variables are integer based. This is an important solver for assignment problems. The final three topics will cover the branch and bound algorithm for integer programming, cutting plane method where fractional values can be utilized in intermediate paths and finally network models for integer programming with focus on transportation and assignment problems.
Topics covered in the lectures would be:
1. Bounded Variables – Simplex Approach.
2. One Dimensional Cutting Stock Problem.
3. Dantzig-Wolfe Decomposition Algorithm.
4. Primal-Dual Algorithm.
5. Goal Programming – Formulations.
6. Integer Programming.
7. Branch and Bound Algorithm.
8. Cutting Plane Algorithm.
9. Transportation Network Models.
10. Assignment Network Model.
11. Shortest Path Problem.
12. Successive Shortest Path Problem.
13. Maximum Flow Problem.
14. Minimum Cost Flow Problem. |
Course Contents |
---|
Lectures:
=========
1. Introduction into operations research
2. Types of problems, application domains
3. Linear programming
4. Integer programming
5. Branch and bound algorithm
6. Cutting plane method
7. Transportation network models
8. Assignment problems
9. Shortest path problem
10. Successive shortest path problem
11. Maximum flow problem
12. Minimum cost flow problem
13. Bio-inspired methods for operations research
14. Continuous and discrete encoding for bio-inspired methods
Seminars:
========
1. Integer programming implementation
2. Application of integer programming for scheduling problems
3. Application of integer programming for logistic problems
4. Implementation of the branch and bound method
5. Application of the branch and bound algorithm for scheduling problems
6. Application of the branch and bound algorithm for routing problems
7. Implementation of the cutting plane method
8. Application of the cutting plane method to integer programming
9. Implementation of a genetic algorithm
10. Application of genetic algorithm to facility location problem
11. Implementation of ant colony optimization
12. Application of ant colony optimization to the minimum cost flow problem
13. Implementation of particle swarm optimization
14. Application of particle swarm optimization to the job shop scheduling problem
|
Recommended or Required Reading |
---|
Required Reading: |
---|
1. Taha Hamdy (2010) Operations Research: An Introduction (9th Edition). ISBN-13: 978-0132555937
2. Winston Wayne (2003) Operations Research: Applications and Algorithms. ISBN-13: 978-0534380588 |
1. Taha Hamdy (2010) Operations Research: An Introduction (9th Edition). ISBN-13: 978-0132555937.
2. Winston Wayne (2003) Operations Research: Applications and Algorithms. ISBN-13: 978-0534380588.
|
Recommended Reading: |
---|
1. Pinedo M. (2012) Scheduling: Theory, Algorithms, and Systems. Springer. ISBN-13: 978-1461419860 |
1. Pinedo M. (2012) Scheduling: Theory, Algorithms, and Systems. Springer. ISBN-13: 978-1461419860 |
Planned learning activities and teaching methods |
---|
Lectures, Tutorials |
Assesment methods and criteria |
---|
Task Title | Task Type | Maximum Number of Points (Act. for Subtasks) | Minimum Number of Points for Task Passing |
---|
Credit and Examination | Credit and Examination | 100 (100) | 51 |
Credit | Credit | 45 | 20 |
Examination | Examination | 55 | 6 |