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

    Belépés
    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: 2024. január 29.

    Budapest University of Technology and Economics
    Faculty of Electrical Engineering and Informatics
    Course ID Semester Assessment Credit Tantárgyfélév
    VISZMA09   2/2/0/v 5  
    3. Course coordinator and department Dr. Fleiner Tamás,
    4. Instructors Padmini Mukkamala, assistant professor, Dept. of Computer Science and Information Theory
    5. Required knowledge basics of linear algebra, graph theory and theory of algorithms 
    6. Pre-requisites
    Kötelező:
    NEM
    (TárgyEredmény( "BMEVISZMA06", "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMEVISZMA06", "FELVETEL", AktualisFelev()) > 0)

    A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

    A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.

    7. Objectives, learning outcomes and obtained knowledge The course provides an introduction to some areas of operations research and combinatorial optimization. Besides describing the main algorithms, methods and their limitations, it aims to provide insights into their technical applications. Thus, it covers areas offering comprehensive algorithmic approaches such as network flow theory and linear and integer programming, but also provides insights into the world of approximation algorithms and scheduling theory, in addition to the higher-order problems that arise in the design of reliable networks. The course also aims to apply and deepen the knowledge previously acquired in the BSc Electrical Engineering course Fundamentals of Computer Science, and to provide a better theoretical background.
    8. Synopsis
    Network flows, Ford-Fulkerson algorithm, integrality lemma,  generalizations of the flow problem.

    Characterization of bipartite graphs, maximum matching in bipartite graphs. Theorems of Kőnig, Frobenius and Hall.

    Graph colourings. Lower and upper bounds on the chromatic number. Edge colouring of graphs, Vizing's theorem. Edge colouring of bipartite graphs using the integrality lemma.

    Egerváry's algorithm for finding maximum total weight matching and perfect matching in bipartite graphs.

    Systems of linear inequalities, basic linear programming, solving bivariate problems by graphical method. Solving linear inequality systems by Fourier-Motzkin elimination. Necessary and sufficient conditions for solving systems of linear equations with non-negative variables and systems of linear inequalities: Farkas' lemma.

    The basic problem of linear programming in matrix form. Necessary and sufficient conditions for the boundedness of the objective function of a linear program. Concept of duality of a linear program, dualities of linear programs written in different forms.

    Duality theorem of linear programming. Algorithmic complexity of the linear programming problem. The basic task of integer programming, its complexity. Formalization of optimization problems as integer programming problems.
     
    Integer programming with a totally unimodular coefficient matrix. Applications in the area of bipartite matchings and network flow problems: maximum flow, minimum cost flow, and multicommodity flow problems.

    The notions of local edge and vertex connectivity and global edge and vertex connectivity, the corresponding Menger theorems (iteration). Max-return order, Nagamochi-Ibaraki's algorithm for determining edge connectivity.

    Algorithm for increasing graphs to be 2-edge-connected, lower bound on the number of edges required. Algorithm for finding minimum cost spanning tree. Ear resolution, directing graphs to ensure strong connectivity.

    Approximation algorithms. Edge chromatic number, approximation of planar graph chromatic number with additive error, approximation of longest cycle with additive error. 2-approximation for the size of covering vertex set, logarithmic approximation for set covering problem.

    Scheduling problems. Basic concepts, notation, useful methods: SPT ordering and list scheduling. FD and FFD heuristics for the crate packing problem.

    Recap, summary, systematic review of the material studied. Description of the current test items for the oral examination and detailed expectations for each item. 
     
     
    9. Method of instruction Lectures and prolem solving.
    10. Assessment

    During the semester:

    There will be two midterms. Both will consist of 4-4 exercises, with a total score of 50 points per test. Both must be at least 20 points to obtain a signature.

    Exam period:

    You can apply for the exam if you have a valid signature. If a signature is obtained, the student is offered a mark based on the total number of marks obtained in the final examination, as follows: from 40 points satisfactory, from 55 to medium, from 70 to good and from 85 to excellent. The lecturer must be informed of the acceptance of the grade offered during the make-up week. Those who accept the grade offered will not be allowed to sit the oral examination. Anyone who does not notify the lecturer of the acceptance of the mark may obtain the mark in the oral examination. In the oral examination, you may improve the grade offered by up to one mark, and you may lower it without limit.

    11. Recaps There will be a retake for both midterms.
    12. Consultations By appointment.
    14. Required learning hours and assignment
    Kontakt óra56
    Félévközi készülés órákra44
    Felkészülés zárthelyire30
    Házi feladat elkészítése
    Kijelölt írásos tananyag elsajátítása
    Vizsgafelkészülés20
    Összesen150
    15. Syllabus prepared by Tamás Fleiner, professor, Dept. of Computer Science and Information Theory