vissza a tantárgylistához   nyomtatható verzió    

    Combinatorial Optimization

    A tantárgy neve magyarul / Name of the subject in Hungarian: Kombinatorikus optimalizálás

    Last updated: 2025. október 20.

    Budapest University of Technology and Economics
    Faculty of Electrical Engineering and Informatics     		MSc Computer Engineering
    Course ID Semester Assessment Credit Tantárgyfélév
    VISZM029   3/1/0/v 5  
    3. Course coordinator and department Dr. Szeszlér Dávid,
    Web page of the course https://www.cs.bme.hu/rendszeropt/
    4. Instructors
    Dr. Viktória Kaszanitzky, Associate Professor, Faculty of Computer Science and Information Theory 
    Dr. András Recski, Professor Emeritus, Faculty of Computer Science and Information Theory 
    Dr. Dávid Szeszlér, Associate Professor, Faculty of Computer Science and Information Theory 
    Dr. Gábor Wiener, Associate Professor, Faculty of Computer Science and Information Theory 
    5. Required knowledge Basics of linear algebra, graph theory, and algorithm theory
    7. Objectives, learning outcomes and obtained knowledge
    The subject provides an introduction to some areas of operations research and combinatorial optimization. Besides presenting the main algorithms, methods, and their limitations, it aims to demonstrate their practical application possibilities. The main topics covered by the subject include linear and integer programming, approximation algorithms, and scheduling algorithms.
    Another objective of the subject is to apply and deepen the knowledge acquired during the Introduction to Computer Science 1 and 2, and Theory of Algorithms courses of the Bachelor of Science in Engineering Informatics program, and to illuminate their theoretical background.
    8. Synopsis
    1-2. Linear and integer programming: Review of the augmenting path algorithm for finding maximum matching in a bipartite graph. Egerváry's algorithm for finding maximum weight matching and perfect matching in bipartite graphs.
    3-4. Linear and integer programming: Basic tasks of linear programming, questions of solvability and boundedness. Graphical solution of two-variable linear programming tasks. Complexity of linear programming. Formalization of practical problems as linear programming tasks.

    5-6. Linear and integer programming: Basic tasks of integer programming, their complexity. Branch and Bound method for solving integer programming problems. Formalization of practical problems as integer programming tasks.

    7-8. Linear and integer programming: Matrix form of linear programming's basic task. Necessary and sufficient conditions for solvability of linear equation systems with non-negative variables, and for solvability of linear inequality systems: Farkas' lemma.

    9-10. Linear and integer programming: Necessary and sufficient conditions for boundedness of the linear program's objective function. Duality theorem of linear programming.

    11-12. Linear and integer programming: Formalization of network flow problems as linear programming tasks: maximum flow, minimum cost flow, and multi-commodity flow problems.

    13-14. Linear and integer programming: Integer programming with totally unimodular coefficient matrices. Applications to problems related to matching in bipartite graphs, network flows, and interval system coloring.

    15-16. Approximation algorithms: Handling NP-hard problems. Polynomial-time solvable special cases of NP-hard problems: resource scheduling, maximum independent set, edge coloring.

    17-18. Approximation algorithms: Concept of approximation algorithms with additive error. Approximation algorithms with additive error for coloring problems, task of finding the longest cycle. Concept of approximation algorithms with multiplicative error, maximum matching problem.

    19-20. Approximation algorithms: Minimum vertex cover problem. Weighted set cover problem: NP-hardness, approximation algorithms.

    21-22. Approximation algorithms: Steiner trees: approximation algorithms for metric and general cases. Traveling salesman problem, 2-approximation algorithm for the metric case.

    23-24. Approximation algorithms: Christofides' algorithm for the metric traveling salesman problem. Concept of fully polynomial approximation schemes, subset sum problem.

    25-26. Scheduling algorithms: Types of scheduling tasks. Single-machine scheduling, list scheduling algorithm for parallel machines. List scheduling by LPT rule, with and without precedence constraints, and Hu's algorithm.

    27-28. Review, summary, systematic overview of the material learned. Explanation of the current exam topic list and detailed expectations regarding individual exam topics.
    9. Method of instruction
    4 hours of lecture per week
    Independent problem-solving takes place during the second half of each lecture.
    10. Assessment
    During the term:
    Midterm exam:

    We will have only one midterm exam during the semester. The prerequisite for obtaining a midterm signature is to achieve at least 40% on the midterm exam.

    Major homework:

    We assign two major homework assignments: one from the linear and integer programming part, and one from the approximation and scheduling algorithms part. The solution of these tasks requires practical application of the relevant learned material. Submitting and acceptance of the major homework assignments is a prerequisite for receiving the recommended grade for the subject (see below).

    Signature from a previous semester:

    Students who have a valid signature from a previous semester may attempt to retake the midterm to improve their previous midterm results. The following conditions apply in this case:

    If the conditions for obtaining the signature again are met, then the result obtained in this way will count towards the exam grade (even if it is worse).
    If it is not possible to meet the conditions for obtaining the signature again, then the signature is not lost, but only the minimum score required to obtain the signature will be counted towards the exam grade.
    If a student with a valid signature appears in at least one midterm during the current semester, it is considered that he/she attempted to meet the conditions for obtaining the signature again (and the above conditions apply). Otherwise, the performance of the last semester when the student attempted to meet the conditions for obtaining the signature will be considered.

    During the exam period:

    The subject grade can be obtained in two ways.

    Recommended grade:

    To obtain a recommended exam grade, two conditions must be met:

    submission and acceptance of the two major homework assignments (see above);
    achieving at least 55% on the midterm (including make-up exams).
    For those who meet these criteria, we offer the following recommended exam grades based on their midterm performance:

    55% or more: pass,
    70% or more: satisfactory,
    85% or more: good
    exam grades.

    A recommended grade cannot be obtained during the exam course.

    Oral exam:

    Students who have a signature but did not obtain (at least satisfactory) a recommended exam grade based on the midterm and major homework, or who want to improve their obtained recommended grade, can take an oral exam during the exam period. If a student registers for the exam in Neptun, his/her recommended grade will no longer be considered valid. In this case, the result of the midterm will be considered in the exam grade with a weight of 40%.
    11. Recaps
    The midterm can be made up for by taking a makeup midterm during the term or by taking a paid makeup opportunity during the makeup week. Previously written and successful midterms can also be attempted to be improved during makeup, but with the condition that in this case the new score will always be valid, even if it is worse than the original. There is one exception to this rule: if a student achieves at least 40% on the midterm required for the signature, but the new score for the makeup midterm is below 40%, then the student will still receive the signature, but the midterm score will be considered as 40% in the exam. However, if a student achieves at least 55% on a midterm and then achieves less than 55% on a makeup midterm, the recommended grade (as described above) will be lost.
    The submitted but not accepted major homework assignments can be resubmitted any number of times until they are accepted. The deadline for submitting the major homework assignments is the last working day before the makeup week.
    12. Consultations By appointment.
    13. References, textbooks and resources Foulds, L. R. (2012). Combinatorial optimization for undergraduates. Springer Science & Business Media.
    14. Required learning hours and assignment
    Kontakt óra56
    Félévközi készülés órákra28
    Felkészülés zárthelyire18
    Házi feladat elkészítése12
    Kijelölt írásos tananyag elsajátítása36
    Vizsgafelkészülés150
    Összesen
    15. Syllabus prepared by Dr. Dávid Szeszlér, Associate Professor, Faculty of Computer Science and Information Theory