Combinatorial Optimization

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.