optimization Archives - Page 5 of 5

How I Solved the Shortest Superstring Problem in Excel

A while back I wrote an introduction to the shortest superstring problem and promised two follow-ups: one showing the greedy algorithm I wrote in VBA, and another showing how I bolted optimization on top to do better than greedy alone. Then I did what I usually do with “future work” and let it sit. Here, finally, is that follow-up — the whole thing in one post, because this is really the story of how I solved the shortest superstring problem in Excel with two stages of the same machine: a VBA pass that generates candidates, and an optimization model that picks the best of them.

Continue reading “How I Solved the Shortest Superstring Problem in Excel”

The shortest superstring problem

I was introduced to the shortest superstring problem by a request I got on Fiverr. The request turned out to be a waste of time but I really enjoyed learning about it.

Problem statement

The shortest common superstring problem aims to find a string with a minimal length that contains every string in a given set.

Hall’s Marriage Theorem Meets the DraftKings Entry Form

This is the last post in my accidental Fourier-Motzkin trilogy (part one: the method; part two: the baseball lineups), and it’s about the bill coming due. Because when you use elimination to throw variables out of a model, the mathematics is very clear about what you keep — and very quiet about what you lose. I found out exactly what I’d lost the first time DraftKings rejected a lineup my spreadsheet swore was legal. The story runs straight through a beautiful piece of combinatorics called Hall’s marriage theorem, so we’ll pick that up along the way.

A Fourier-Motzkin Elimination Example: DraftKings Lineups

In my last post about Fourier-Motzkin elimination I promised a real example involving baseball, and I keep my promises. This is the story of how a dusty 19th-century math trick ended up picking my daily fantasy lineups — and how I stumbled into a genuine Fourier-Motzkin elimination example without fully realizing that’s what I was doing until much later.

Continue reading “A Fourier-Motzkin Elimination Example: DraftKings Lineups”

Fourier-Motzkin Elimination: An Old Trick I Still Use

Fourier-Motzkin elimination is one of those methods that gets a page and a half in the linear programming textbooks, right before the simplex method shows up and steals the whole show. I was first introduced to it while working as an OR analyst at Cargill, and my honest first reaction was: nice, but why would I ever use this? It took me years (and one very stubborn model) to change my mind. This post is the explanation I wish someone had given me back then: what the method actually does, how the mechanics work, and a small worked example showing a model before and after the elimination.

Continue reading “Fourier-Motzkin Elimination: An Old Trick I Still Use”