BME VIK - Kombinatorikus optimalizálás

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 www.cs.bme.hu/....

4. Instructors

Name	Position	Department
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 11^th 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 : szeszler@cs.bme.hu

13. References, textbooks and resources

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

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

14. Required learning hours and assignment

Number of contact hours	56
Preparation to the classes	18
Preparation to the tests	10
Homework	16
Assigned reading
Preparation to the exam	20
Total	120

15. Syllabus prepared by

Name	Position	Department
Dávid SZESZLÉR	Assoc. professor	Department of Computer Science and Information Theory

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

Kombinatorikus optimalizálás