Tag Archives: Linear Programming
Linear Programming (Trek through Math 1/8)
The Secretary/Toilet Problem and Online Optimization
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
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
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
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
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
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
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
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!