optimization Archives - Page 10 of 11

What is mathematical programming

Mathematical programming is a field of mathematics that deals with the optimization of complex systems and processes. It has a rich history that dates back to the 1940s when George Dantzig, an American mathematician, developed the simplex method for solving linear programming problems. Since then, it has grown into a vast and dynamic discipline that has found applications in various fields such as finance, transportation, engineering, and operations research.

In this blog post, I will explore the origins of mathematical programming, provide an example of a problem that can be tackled and list some classical problems. I will also discuss some of the software products used in mathematical programming, both open-source and commercial.

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”