460-4108/01 – Operations Research II (OV II)

Gurantor departmentDepartment of Computer ScienceCredits4
Subject guarantordoc. Ing. Pavel Krömer, Ph.D.Subject version guarantordoc. Ing. Pavel Krömer, Ph.D.
Study levelundergraduate or graduateRequirementOptional
Year2Semesterwinter
Study languageCzech
Year of introduction2015/2016Year of cancellation
Intended for the facultiesFEIIntended for study typesFollow-up Master
Instruction secured by
LoginNameTuitorTeacher giving lectures
KRO080 doc. Ing. Pavel Krömer, Ph.D.
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Credit and Examination 2+2
Combined Credit and Examination 10+0

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

Další požadavky na studenta

Additional requirements are placed on the student.

Prerequisities

Subject codeAbbreviationTitleRequirement
460-4062 OV Operational Research I Recommended

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

Combined form (validity from: 2015/2016 Winter semester)
Task nameType of taskMax. 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
Mandatory attendence parzicipation:

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.FormStudy language Tut. centreYearWSType of duty
2019/2020 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2019/2020 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2018/2019 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2018/2019 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2017/2018 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2017/2018 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2016/2017 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2016/2017 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2015/2016 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2015/2016 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner