3
$\begingroup$

I am wondering what examples you like to give when introducing linear programming, where the examples are not clearly better suited as integer linear programs. I would like a few examples where we can discuss the motivating story, then formalize and write it down as an LP.

  • I can motivate production problems as LPs, when I am careful to phrase everything in terms of rates: rate of resources consumed per day, rate of products produced per day, maximizing rate of profit per day. This way, fractional solutions make sense. Same for their duals (min-cost procurement).
  • I will use zero-sum games as a more intricate example.

But:

  • I think scheduling and assignment problems are generally better as ILPs.
  • Flows, paths, and matchings deserve their own separate discussion in my opinion, due to the Integrality Theorem.

It seems like most practically motivating applications are scheduling and assignment problems that really should be ILPs. What are your favorite motivating LP applications? I also appreciate thoughts about how to navigate this question pedagogically, for example if your approach is to just motivate ILPs and treat LPs as a means to an end.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

[Chris, convert to comment, if you deem. /Not cookie mousing.]

I think you are best off for an intro to do an example that is extremely simple and toy-like and might even be simply solved by high school algebra (but allows describing a logistical problem and drawing a sketch). The students are new to the techniques.

Something like this, but then use the simplex method (don't prove it now, leave for later...for now, just assert it and use it) at the end:

https://www.youtube.com/watch?v=M_mpRrGKKMo

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Yes, thanks, I agree with this. In my question, I am thinking more of the third, fourth, fifth examples they see, to illustrate the power of the technique. We wouldn't try to solve them by hand, just practice modeling problems as LPs. $\endgroup$
    – usul
    Commented Aug 16, 2022 at 16:20
  • $\begingroup$ If the example has only 2 decision variables, then you can draw it with one decision variable on the x-axis and the other on the y-axis. The feasible region will be represented as a polygon, and the objective function will be represented as a direction vector. The optimal solution is the point which is most in that direction; this is very easy to visualise, and you can draw the perpendicular to the direction vector going through that point to prove that it is really optimal. $\endgroup$
    – Stef
    Commented Sep 5, 2022 at 15:00
  • $\begingroup$ @usul "We wouldn't try to solve them by hand, just practice modeling problems as LPs" You can find a very user friendly free online LP solver at online-optimizer.appspot.com So, if you want your students to actually see the results of their modeling, I would recommend considering using it at least in the demonstration mode where you are at the controls yourself (though the syntax of the corresponding programming language is not hard to learn from numerous examples you can find on the site) $\endgroup$
    – fedja
    Commented Jan 16, 2023 at 3:56
  • $\begingroup$ Thanks, @fedja! $\endgroup$
    – usul
    Commented Jan 16, 2023 at 5:42

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.