Course Announcement

# MA421: "Linear Programming and Optimization Techniques"

To be offered Spring 2010

Instructor: Prof. Walther

MA 421 will discuss a collection of questions generally referred to as "optimization problems". In all cases, one wants to minimize or maximize a certain quantity while having to deal with constraints. The constraints may be equalities or inequalities.

This sort of problem was not much considered before the middle of the 20th century; its early main heros are the Russian mathematician Leonid Kantorovich, American mathematicians George Dantzig and John von Neumann (remember "Good will hunting"?!), and the Hungarian mathematicians Denes Koenig, Gyula Farkas and Jeno Egervary.

The Hungarian school initiated what is today referred to as "discrete optimization" while Kantorovich, Dantzig and von Neumann mostly created "linear programming". In the "discrete" setting, one faces (for example) the "knapsack problem": you are going camping and have a backpack of finite size. In your apartment you have many items you might want to take: tooth brush, XBox, sleeping bag, TV, etc. Some are big, some small, some you need, some you just like. What is the best way to pack your bag? In other words, which items will fit in the backpack and give you the most joy? The problem is that each item is either "in" or "out".

In the "linear" case, you are entitled to take fractional parts of things, which simplifies life enormously.

Optimization techniques save significant amounts of money every day.

The wiki for this course is here.