2V300: discrete optimization and linear programming

Introduction to combinatrial optimization and to the use of linear programming

This text describes the procedure to successfully handle the course material and assignments for the course Discrete optimization and Linear Programming. For a Dutch description and set of assignments click .
Deze tekst bevat een beschrijving over de afhandeling van het homologatievak discrete optimalisering en lineaire programmering. Voor de Nederlandstalige vakbeschrijving en opgaven-set klik op .

2V300 is a preparation course for the graduate course Logistieke Besturingssystemen. By means of study and exercises the students will becme acquainted with the major principles of discrete optimization. Unless exempted for this course, the students have to study the materials by themselves, and make the exercises - in couples of at most two - and deliver a report before the end of their first semester. The reports will be discussed by the student and professor Hurkens. The initiative to deliver the reports in time and too make an appointment for discussing the report has to come from the students.

The first more theroretical part concerns modelling. In many logistic problems in real life the first step is to identify the essentials of hte problem and to cast it into some mathematical framework. Often, one arrives at classical mathematical operations research models as "maximum flow in a graph", transhipment, or scheduling. Some of these problems allow for a greedy or polynomial time combinatorial algorithms, others easily translate to (integer) linear programming models. We discuss several standard problems, standard-models and standard methods.

As course material for this first theoretical part we make use of a set of lecture notes with an introduction in discrete optimization. It covers a number of theoretical models, as well as algorithms. The material is a major subset of the course material for Management Science students of the rgular course "Optimaliseringsmethoden" (2P350). Lecture notes are in English only.

For the LBS student a number of exercises has been selected, which together with the lecture notes, can be found in LBS lecture notes and exercises. Exercises and material description come in both Dutch and English versions.

The second part concerns a practical exercise in the use of Linear Programming models and packages. These form a widely applied toolbox for various operational and logistical problems. An overview and reference to litterature, course materials and assignments is found in the LBS introduction to linear programming.

Theoretical and practical assignments should be worked out in a report that should be submitted (hard-copy only) to professor Hurkens, Department of Mathematics, HG.9.29, tel 4771, email to wscor@win.tue.nl. An appointment to discuss the report should be made. Each student is graded individually.