Linear Programming

Some years ago, I worked on real-time meal delivery at Zoomer, a YC startup based out of Philadelphia. Zoomer’s production tech stack was primarily Ruby. As it grew we moved from using heuristics for things like routing and scheduling to open source optimization solvers. Like most languages that aren’t Python, Ruby doesn’t have an especially mature ecosystem for optimization (or data science, or machine learning, for that matter). For some use cases that didn’t matter. When we upgraded the routing engine, we built a model in C++ using Gecode and wrapped a Ruby gem around a SWIG wrapper. But when we wanted to use integer programming to build schedules, the lack of solver APIs proved inconvenient.1 ...

Note: This post has been updated to work with HiGHS. A fun geometry problem to think about is: given two polygons, do they intersect? That is, do they touch on the border or overlap? Does one reside entirely within the other? While this question has obvious applications in computer graphics (see: arcade games of the 1980s), it’s also important in areas such as cutting and packing problems. There are a number of way to answer this. In computer graphics, the problem is often approached using a clipping algorithm. This post examines a couple of simpler techniques using linear inequalities and properties of convexity. To simplify the presentation, we assume we’re only interested in convex polygons in two dimensions. We also assume that rotation is not an issue. That is, if one of the polygons is rotated, we can simply re-test to see if they overlap. ...

Note: This post was originally written using Julia v0.2, GLPK, and Hedonometer data through 2014. It has been updated to use Julia v1.11, HiGHS, and data through May 26, 2025. Hedonometer popped onto my radar a couple weeks ago. It’s a nifty project, attempting to convert samples of words found in the Twitter Gardenhose feed into a time series of happiness. While I’m not a computational social scientist, I must say the data does have a nice intuitive quality to it. There are obvious trends in happiness associated with major holidays, days of the week, and seasons. It seems like the sort of data that could be decomposed into trends based on those various components. The Hedonometer group has, of course, done extensive analyses of their own data which you can find on their papers page. ...

Note: This post was updated to work with Python 3 and PySCIPOpt. The original version used Python 2 and python-zibopt. Data fitting is one of those tasks that everyone should have at least some exposure to. Certainly developers and analysts will benefit from a working knowledge of its fundamentals and their implementations. However, in my own reading I’ve found it difficult to locate good examples that are simple enough to pick up quickly and come with accompanying source code. ...