Operations Research

COURSE OBJECTIVE
Acquaint the student with the use of mathematical techniques for solving deterministic optimization problems. Subjects studied are:

• Modelling with linear and integer linear optimization
• Modelling with dynamic programming
• Solution methods for the resulting mathematical optimization problems
• Basic problems from discrete optimization and their solution methods

COURSE CONTENT
The course is a first introduction to optimization problems. We start with linear optimization. Many practical problems allow mathematical formulation as optimization of some linear objective function in decision variables subject to a set of linear constraints in these decision variables. A central theme will be the art of formulating a verbally described practical problem as a linear optimization problem and interpreting the mathematical solution within the original problem. The simplex algorithm for solving the mathematical model will be studied and correctness of this algorithm will be argued.

The modeling power of the linear optimization model will be enhanced by introducing integrality restrictions on decision variables. The branch- and-bound method for solving integer linear optimization will be studied.

Some basic problems from discrete optimization will be presented, with an emphasis on network optimization problems for which efficient algorithms exist, like the shortest path problem, the maximum flow problem and the assignment problem. The student will get acquainted with determining the running time of algorithms and the very basics of computational complexity theory.

Integer linear optimization is without doubt the most popular technique for solving harder discrete optimization problems. As an alternative we present dynamic programming, which is both a modeling technique and a solution technique.

TEACHING METHODS
Lectures, instructions

During classes the material will be presented based on the book. Lecture notes provided will supplement the book. The instructions are self-active, meaning that students will work on exercises themselves and have the opportunity to ask questions to and hints from the instructors. In rare cases, after noticing common difficulties, instructors may show solutions on the blackboard. The last part of every instruction is devoted to a small selection of exercises that students make in groups of 2 or 3 and hand in for marking.

TYPE OF ASSESSMENT
Exercises to be made weekly during instruction comprise 25% of the final mark. A written final exam will constitute the remaining 75% of the final mark.