8
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ Something like a static/deterministic version of Tetris $\endgroup$
    – PeterD
    Commented Apr 9, 2022 at 8:30
  • 1
    $\begingroup$ Continuous LP only, or also MILP? $\endgroup$
    – Mark L. Stone
    Commented Apr 9, 2022 at 15:30
  • $\begingroup$ @MarkL.Stone sorry, definitely MILPs as well. $\endgroup$
    – Mason
    Commented Apr 9, 2022 at 17:32
  • $\begingroup$ 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. $\endgroup$
    – prubin ♦
    Commented Apr 9, 2022 at 20:04
  • $\begingroup$ There are a few questions already about puzzles that can be solved using OR. I just created a puzzles-games tag for them. $\endgroup$
    – LarrySnyder610
    Commented Apr 11, 2022 at 0:49

4 Answers 4

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is great, exactly what I was interested in. Thanks for the reply! $\endgroup$
    – Mason
    Commented Apr 9, 2022 at 17:38
5
$\begingroup$

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)?
Improve this answer
$\endgroup$
4
$\begingroup$

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

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.