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?

$\endgroup$
5
  • $\begingroup$ Something like a static/deterministic version of Tetris $\endgroup$
    – PeterD
    Apr 9, 2022 at 8:30
  • 1
    $\begingroup$ Continuous LP only, or also MILP? $\endgroup$ Apr 9, 2022 at 15:30
  • $\begingroup$ @MarkL.Stone sorry, definitely MILPs as well. $\endgroup$
    – Mason
    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
    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$ Apr 11, 2022 at 0:49

4 Answers 4

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.

$\endgroup$
1
  • $\begingroup$ This is great, exactly what I was interested in. Thanks for the reply! $\endgroup$
    – Mason
    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)?
$\endgroup$
4
$\begingroup$

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

$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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