Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

    címtáras azonosítással

    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: 2010. november 11.

    Budapest University of Technology and Economics
    Faculty of Electrical Engineering and Informatics

    Mérnök informatikus szak

    BSc képzés

    Course ID Semester Assessment Credit Tantárgyfélév
    VISZA080   3/1/0/v 4  
    3. Course coordinator and department Dr. Szeszlér Dávid,
    Web page of the course
    4. Instructors






    Dávid SZESZLÉR


    Assoc. professor


    Department of Computer Science and Information Theory


    Gábor WIENER


    Assoc. professor


    Department of Computer Science and Information Theory


    Tamás FLEINER


    Assoc. professor


    Department of Computer Science and Information Theory


    Ildikó SCHLOTTER


    Assistant lecturer


    Department of Computer Science and Information Theory


    7. Objectives, learning outcomes and obtained knowledge

    The objective of the first part of this course is to introduce the basic notions and give a glimpse of the range of applicability of linear and integer programming. Students will be given the chance to model and solve a miniature of a real–life problem that comes from the world of business or industry.


    The objective of the second half of this course is to give a deeper insight into the theory of linear and integer programming and cover more involved applications. Furthermore, certain graph-theoretic results (covered by VISZA086 – Graph theory) will be put into a more general context and various generalizations will be dealt with.


    8. Synopsis

    First half-semester
    1. Introduction
        Solving systems of linear equations with the Gaussian elimination
        Detecting solvability and uniqueness, numerical examples
    2. Matrices, fundamental operations on matrices
        Inverse matrix, deciding the existence and determining the inverse
    3. The basic problem of linear programming
        Graphic solution in case of two variables: sketching the feasible region, maximizing the objective function
    4. Modeling practical problems as multivariable LP instances
        Solving LP problems with Microsoft Excel
        Interpreting the Sensitivity Report of the Excel output
    5. The notion of integer programming
        Modeling practical problems as IP instances
        Using decision variables, incorporating logical constraints
    6. The matrix form of LP/IP problems
        Solving systems of linear inequalities with the Fourier-Motzkin elimination

    Second half-semester
    7. A necessary and sufficient condition for the solvability of systems of linear inequalities: Farkas'lemma.       Equivalent forms of the lemma.
    8. The concept of duality in linear programming.
        The duality theorem.
    9. An application: the Ford-Fulkerson theorem for the maximum flow problem.
        Generalizations of the flow problem: minimum cost flow, multicommodity flow.
    10. Algorithmic complexity of the linear and integer programming problems.
          In-class test.
    11. The branch and bound method for integer programming.
    12. The optimum assignment problem and the maximum weight bipartite matching problem.
          Hungarian method, Egerváry's algorithm.

    9. Method of instruction Lectures and recitations


    10. Assessment Students are required to solve and hand in the full documentation of a small LP or IP problem. The solution should contain the major steps of forming the LP/IP model, the Excel worksheet created for solving the problem and an interpretation of the output in terms of the original problem statement.



    There will be an in-class test on the 11th week. The test aims at ensuring the firm knowledge and understanding of the necessary notions and theory covered through simple numerical exercises.



    Grading will be based on the following criteria:


    – Final exam                                                                                30 points


    – Solution of the individually assigned LP/IP problem                    30 points


    – In-class test                                                                              30 points


    – Class participation                                                                    10 points



    12. Consultations You can reach the instructor at the following e-mail address for consultation:


    Dávid SZESZLÉR :


    13. References, textbooks and resources

    Hillier, Lieberman: Introduction to Operations Research, McGraw – Hill, 2005 (8th ed.)

    Matoušek, Gärtner: Understanding and using linear programming, Springer, 2007.


    14. Required learning hours and assignment
    Number of contact hours




    Preparation to the classes




    Preparation to the tests








    Assigned reading




    Preparation to the exam








    15. Syllabus prepared by






    Dávid SZESZLÉR


    Assoc. professor


    Department of Computer Science and Information Theory