8

I am interested in common problems/puzzles that have a clear set of rules/constraints and objective that lends itself to modeled and solved with a linear program. Especially for people new to LPs, I think that translating a tangible problem into a mathematical formulation is one of the best ways to explain the applicability of LPS.

Some easy examples I can think of would be sudoku and the 8-queens puzzle. What are other examples that come to mind?

LarrySnyder610
  • 13,141
  • 3
  • 41
  • 105
Mason
  • 515
  • 4
  • 8
  • Something like a static/deterministic version of Tetris – PeterD Apr 09 '22 at 08:30
  • 1
    Continuous LP only, or also MILP? – Mark L. Stone Apr 09 '22 at 15:30
  • @MarkL.Stone sorry, definitely MILPs as well. – Mason Apr 09 '22 at 17:32
  • One concern about using puzzles like sudoku to explain the applicability of LP and MILP models is that they do not have meaningful objective functions. You are solving for any (or, more commonly, the unique) feasible solution, not for a "best" solution among many. – prubin Apr 09 '22 at 20:04
  • There are a few questions already about puzzles that can be solved using OR. I just created a [tag:puzzles-games] tag for them. – LarrySnyder610 Apr 11 '22 at 00:49

4 Answers4

9

I do this all the time over at https://puzzling.stackexchange.com/. Currently, a search for "linear programming" yields 44 results. Most of these actually use integer linear programming, and several involve chessboard problems. But here's one that uses LP and has a nice animation: https://puzzling.stackexchange.com/questions/111297/five-friends-and-two-motorcyclists/111301#111301

See also these posts, where I have used LP duality to provide short certificates of optimality for various puzzles.

RobPratt
  • 32,006
  • 1
  • 44
  • 84
5

Some other puzzles that you can solve with (MI)LPs:

enter image description here

  • Suppose an electronic lock has 3 digits, and that the lock opens once the right code is entered, no matter what was tried just before. What is the fastest way to open the lock (the shortest sequence of numbers that will open the lock)?
Kuifje
  • 13,324
  • 1
  • 23
  • 56
4

Also these posts are all linear optimization problems using Pyomo https://www.linkedin.com/newsletters/optimization-in-open-source-6874020019009859585/

Optimization team
  • 1,326
  • 1
  • 6
  • 20
2

You can formulate construction of latin squares as an (integer) linear programming problem. Extending that, you can get sudokus this way.

I have some code for the latin square part, which I will dig up later to complete this answer.

kjetil b halvorsen
  • 718
  • 1
  • 7
  • 24