Gurantor department | Department of Computer Science | Credits | 4 |

Subject guarantor | doc. Ing. Pavel Krömer, Ph.D. | Subject version guarantor | doc. 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 |

Instruction secured by | |||
---|---|---|---|

Login | Name | Tuitor | Teacher giving lectures |

KRO080 | doc. Ing. Pavel Krömer, Ph.D. |

Extent of instruction for forms of study | ||
---|---|---|

Form of study | Way of compl. | Extent |

Full-time | Credit and Examination | 2+2 |

Combined | Credit and Examination | 10+0 |

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.

Lectures

Tutorials

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.

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. Pinedo M. (2012) Scheduling: Theory, Algorithms, and Systems. Springer. ISBN-13: 978-1461419860

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.

Additional requirements are placed on the student.

Subject code | Abbreviation | Title | Requirement |
---|---|---|---|

460-4062 | OV | Operational Research I | Recommended |

Subject has no co-requisities.

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

Task name | Type of task | Max. number of points
(act. for subtasks) | Min. number of points |
---|---|---|---|

Credit and Examination | Credit and Examination | 100 (100) | 51 |

Credit | Credit | 45 | 20 |

Examination | Examination | 55 | 6 |

Show history

Academic year | Programme | Field of study | Spec. | Form | Study language | Tut. centre | Year | W | S | Type of duty | |
---|---|---|---|---|---|---|---|---|---|---|---|

2019/2020 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | P | English | Ostrava | 2 | Optional | study plan | |||

2019/2020 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | K | English | Ostrava | 2 | Optional | study plan | |||

2018/2019 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | P | English | Ostrava | 2 | Optional | study plan | |||

2018/2019 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | K | English | Ostrava | 2 | Optional | study plan | |||

2017/2018 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | P | English | Ostrava | 2 | Optional | study plan | |||

2017/2018 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | K | English | Ostrava | 2 | Optional | study plan | |||

2016/2017 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | P | English | Ostrava | 2 | Optional | study plan | |||

2016/2017 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | K | English | Ostrava | 2 | Optional | study plan | |||

2015/2016 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | P | English | Ostrava | 2 | Optional | study plan | |||

2015/2016 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | K | English | Ostrava | 2 | Optional | study plan |

Block name | Academic year | Form of study | Study language | Year | W | S | Type of block | Block owner |
---|