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

 Budapest University of Technology and Economics Faculty of Electrical Engineering and Informatics Mérnök informatikus szakBSc 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 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 : szeszler@cs.bme.hu

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 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