6 Beyond Legos

In the world of optimization, the Lego furniture problem is known as a resource allocation problem. This is one of the first applications of Linear Programming, and is still an important application in business and military settings. Linear programs have been be used to optimize work schedules, delivery jobs and routes, airline flight routes and schedules, sports schedules, fantasy team lineups, water and gas pipelines, telecommunication networks, election polling locations, pollution mitigation strategies, and the list goes on and on and on.

During World War 2, George Dantzig defined and used linear programs to develop efficient operational plans for the United States Air Force. After the war in 1947, Dantzig published the algorithm, now called the simplex method, that he had developed to efficiently solve linear programs.

Linear programming models that solve real-world problems can easily have thousands or even millions of decision variables, and billions of basic feasible solutions. Fortunately, the simplex method does not require finding every single basic feasible solution like we did. Instead, the simplex method starts at a corner point of the feasible region and traverses a path through adjacent corner points so that the objective function either stays the same or improves at each step. The simplex method terminates when none of the corner points adjacent to the current corner point improves the objective function, indicating that the current solution is optimal. The simplex method is still implemented in top open-source and proprietary linear programming solvers.