460-4108/02 – Operations Research II (OV II)
Gurantor department | Department of Computer Science | Credits | 4 |
Subject guarantor | prof. Ing. Pavel Krömer, Ph.D. | Subject version guarantor | prof. Ing. Pavel Krömer, Ph.D. |
Study level | undergraduate or graduate | Requirement | Optional |
Year | 2 | Semester | winter |
| | Study language | English |
Year of introduction | 2015/2016 | Year of cancellation | |
Intended for the faculties | FEI | Intended for study types | Follow-up Master |
Subject aims expressed by acquired skills and competences
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.
Teaching methods
Lectures
Tutorials
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.
Compulsory literature:
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 literature:
1. Pinedo M. (2012) Scheduling: Theory, Algorithms, and Systems. Springer. ISBN-13: 978-1461419860
Way of continuous check of knowledge in the course of semester
Each student will conceive and submit three assignments on topics related to advanced operations research. The topics of the assignments will include the application of different discussed methods to complex operations research problems. The students will work on the assignments continuously during the course of the term. There will be a possibility to consult the progress and the solutions at the lectures, seminars, individual consultations and by email.
The exam is written.
E-learning
Other requirements
Additional requirements are placed on the student.
Prerequisities
Co-requisities
Subject has no co-requisities.
Subject syllabus:
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
Conditions for subject completion
Occurrence in study plans
Occurrence in special blocks
Assessment of instruction
Předmět neobsahuje žádné hodnocení.