HHC 2021 - Lines and graphs presentation

[Gene]

This was my attempt to explain Linear Programming in its simplest form: 2 unknowns and using graphs to find a solution.

Not sure how many of us have ever used linear programming, but it often seems very complex. It ** is ** very complex for real world problems, but I like to know how it works for simple problems and then assume computers do the same thing I just did for the complicated problems.

Lines and Graphs HHC 2021 - Linear Programming

I taught this in a former life when I was a professor at a local university. Part of the management science class (queuing theory, decision theory, forecasting, simulation).

/sarcasm on -- Undergraduates always loved it. -- /sarcasm off

[David Hayden]

I learned this stuff in an operations research course in college, It was fun to see it again and get a refresher

Regarding why the best solution is always in a corner, one way to see this is to start by thinking of the bounds as a fencediin field. If you add the cost as a third dimension to the graph, then the cost forms a plane and it's like the fenced field is on a slope. No matter how the plane slopes, the low point is always in a corner.

[Gene]

With one caveat - if the slope of the objective function is the same as the slope of line between two corners, then any point along the line should have the same objective function value.

Otherwise, quite correct! :-)

[3298]

Semi-related: Linear programming can be useful in rendering. (Skip this post if you're not interested in that.)

I once wrote a software renderer. Not much came of it afterwards (other than this), but I learned a lot about rendering in the process. It uses Binary Space Partitioning, and a well-performing algorithm for an important function on BSP trees (merging two together) relies on linear programming.

The role of linear programming there is to check if the constraints given by "on this side of this plane, on that side of that plane, etc." can be satisfied by any point at all. If they can't, then the algorithm knows that it's pointless to keep iterating into child nodes of the BSP tree, since points / polygons / nodes will always be outside this impossible space.

In its simplest description (as above), the algorithm uses linear programming in a space with the same dimensions as the trees (i.e. 3D in real-world cases), but I'm proud of the fact that I managed to break it down for my particular implementation into 1-dimensional linear programming. For those who understand BSP in general and want to replicate that:
- When merging BSP trees, you iterate through one tree and repeatedly cut the other along the plane representing the current node. This gives us the opportunity to work in that (2D) plane only, instead of the whole space.
- To cut a tree along a plane, you iterate through that tree and cut each node's plane along the input plane. This is the step where the linear programming problem actually needs to gets solved. Since we're traversing a tree, you can make it so that the solution found for the parent is handed down into the child's problem, and the linear programming problem is shaped such that you can build on this solution by adding a piece that has one less dimension than the whole problem - in each step descending along a tree you add a single constraint, so you only check if that switches the problem from feasible to infeasible.

Anyway, just wanted to get a real-world application of this concept off my chest. Carry on!