Tag Archives: Linear Programming

Linear Programming (Trek through Math 1/8)

January 28, 2016A Trek through 20th Century Mathematics3005 vuesEdit

The Secretary/Toilet Problem and Online Optimization

April 02, 2015Article2243 vuesEdit
A large chunk of applied mathematics has focused on optimizing something with respect to all relevant data. However, in practice, especially in the online world, the data is not available to us, and, yet, we're still expected to make nearly optimal decisions. This problem is exemplified by the famous secretary problem, where a manager needs to decide to hire candidates right after interviews, even though he has not yet met all the candidates. In this article, we review this classic as well as many very recent developments.

Column Generation and Dantzig-Wolfe Decomposition

May 24, 2014Article4479 vuesEdit
Column generation and the Dantzig-Wolfe decomposition are powerful tricks which have revolutionized optimization addressed to industrial problems, and generated millions and millions of dollars. My PhD supervisor effectively took great advantage of these tricks and founded companies with it. This article explains the tricks.

Santa Routing and Heuristics in Operations Research

December 19, 2013Article5514 vuesEdit
Designing routes to visit customers has become one of applied mathematicians' favorite optimization problems, as companies offer millions to solve them! This article discusses the clever technics they have come up with, and use them to help Santa deliver toys to kids all over the world!

Optimization by Integer Programming

September 24, 2013Article4879 vuesEdit
Integer programming is arguably the greatest achievement of applied mathematics. Half of the time, it's what's used to solve real-world problems!

Duality in Linear Programming

June 23, 2012Article13194 vuesEdit
Duality in linear programming yields plenty of amazing results that help understand and improve algorithms of resolution. This article shows the construction of the dual and its interpretation, as well as major results. In particular, matching of primal and dual bases will be dealt, before presenting the issue of degeneracy and its dual interpretation.

Primal and Dual Simplex Methods

June 23, 2012Article9539 vuesEdit
The simplex method is one of the major algorithm of the 20th century, as it enables the resolution of linear problems with millions of variables. An intuitive approach is given. But that's not all. We present an important variant called the dual simplex. Finally, we'll explain its main default, that is, when facing degeneracy.

Dual Variable Stabilization

June 22, 2012Article477 vuesEdit
Simplex methods face issues in case of degeneracy. The dual variable stabilization is a very recent state-of-the-art way to deal with degeneracy. An intuitive understanding is given in this article.

Optimization by Linear Programming

May 23, 2012Article4715 vuesEdit
Operations Research deals with optimizing industrial systems. Those systems can be very complex and their modeling may require the use of hundreds, thousands or even millions of variables. Optimizing over millions of variables may seem impossible, but it can be done if the optimization problem has a linear structure. Learn more on this linear structure and optimization solutions!