Lecture Notes Discrete Optimization

All texts are available in postscript format (with postfix .ps), for which you need an application as GSview or the like. See Aladin Ghostscript for free downloadable applications as GSview and PrintFile.
In addition, all texts are also available in PDF-format, which can be read and printed from the PC with the application Acrobat reader.

The assignments for the theoretical part of discrete optimization concern only the first four chapters of these notes. Chapters 5 and 6 are added for completeness for those taking a special interest. The full lecture notes file contain these additional chapters as well.

• In Chapter 1.ps / Chapter 1.pdf elementary concepts from graph theory are presented. Next some algorithms are described fro finding a shortest spanning tree, and for finding a shortest path.
• In Chapter 2.ps / Chapter 2.pdf some algorithms are presented for solving the maximum (weight) matchingproblem, and the maximum flow problem.
• In Chapter 3.ps / Chapter 3.pdf the linear programming problem is preented, together with a description pof the simplex method to solve the LP. The chapter is based on the book `Linear Programming' van V. Chvatal (1983).
• In Chapter 4.ps / Chapter 4.pdf an illustration is given of some elementary techniques, such as branch-and-bound and dynamic programming, and several complexity concepts are described such as worst-case analysis and NP-completeness. Examples are demonstrated considering the knapsack problem.
• In Chapter 5.ps / Chapter 5.pdf we find several aspects of the well-kown traveling salesman problem.
• In Chapter 6.ps / Chapter 6.pdf scheduling theory is introduced.
• Complete lecture notes (including chapters 5 and 6) are available in postscript as well as PDF-format.

• Theory of combinatorial optimization exercises for 2V300.ps / Theory of combinatorial optimization exercises for 2V300.pdf.
• For the practical problems in linear programming we refer to the web-pages with the LP-assignments.