most recent 30 from http://mathoverflow.net 2013-05-21T00:57:50Z http://mathoverflow.net/feeds/question/27015 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/27015/is-it-possible-to-use-linear-programming-to-solve-this-problem unknown (google) 2010-06-04T05:36:36Z 2010-06-04T06:11:41Z

<p>I am trying to write software to minimize pricing for cell phone subscription services, ie: choose the optimum plan for each customer in a large group. </p> <p>Could someone comment on whether this is possible via linear programming?</p> <p>Here is a description of the problem (the numbers in the examples may not be realistic so try to ignore that): </p> <p>Base Plan Options </p> <pre><code>Plan A: 200 Voice minutes, 10 Text Messages, 10 MB Data = $25 Plan B: 400 Voice minutes, 25 Text Messages, 25 MB Data = $40 Plan C: 1000 Voice minutes, 50 Text Messages, 50 MB Data = $65 ... Plan F: 2500 Voice minutes, 150 Text Messages, 150 MB Data = $95 </code></pre> <p>Charges for exceeding your plan (for all cases): </p> <pre><code>$.10 per voice minute $.20 per text message $1.50 per MB Data </code></pre> <p>Optional Add-On Packages (added to Base Plan): </p> <pre><code>Free Weekends $15 Free Evenings and Weekends (after 8PM) $20 Free Evenings and Weekends (after 6PM) $35 Text Message Package #1 (50 Text Messages) $5 Text Message Package #2 (150 Text Messages) $10 Data Package #1 (20 MB Data) $20 Data Package #2 (50 MB Data) $30 Chatty User Mixed Pack #1 (100 Minutes Voice, 100 Text Messages) $15 Geeky User Mixed Pack #1 (50 Minutes Voice, 150 MB Data) $35 etc, etc etc </code></pre> <p>So if I have a set of detailed usage data for say 500 users, I want to figure out which combination of base plan (A, B, C ... F) each person should be on, as well as which add-on packages(s) they should have.</p> <p>In the base packages and optional add-ons examples I gave, I was trying to make the point that there are so many overlapping options that brute force calculation of each option for each user is impractical.</p> <p>So my question is, can this somehow be done efficiently via linear programming?<br> And if so, I would greatly appreciate any hints or direction on where an experienced software developer with no expertise in linear programming might start?</p> <h2>Update</h2> <p>Thanks for the helpful comments so far. Thanks to DoubleJay I now know this is an integer programming problem. And yes, I most definitely will use a 3rd party solver, I need one that is callable from .Net platform, so if anyone has any suggestions on an affordable one let me know.</p> <p>Once I have the solver, figuring out how one declares this problem within is my next problem, so any tips on where one would begin learning would also be much appreciated.</p> <p>(Am also trying stackoverflow, but thought there'd likely be more expertise here for this particular problem).</p>