4
$\begingroup$

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.

Could someone comment on whether this is possible via linear programming?

Here is a description of the problem (the numbers in the examples may not be realistic so try to ignore that):

Base Plan Options 

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

Charges for exceeding your plan (for all cases): 

$.10 per voice minute  
    $.20 per text message  
$1.50 per MB Data

Optional Add-On Packages (added to Base Plan): 

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

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.

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.

So my question is, can this somehow be done efficiently via linear programming?
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?

Update

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.

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.

(Am also trying stackoverflow, but thought there'd likely be more expertise here for this particular problem).

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ No, this requires integer programming. Unless you have a couple spare weeks to devote to the problem, don't program the solver yourself - use someone else's. As for how to do it? That's kind of complicated to explain. Basically, you'll want decision variable for voice, text and data usage, with an objective function piecewise linear in those three plus fixed costs based on the add-ons (which are determined by logical integer constraints (e.g. min FREE WEEKENDS, WEEKEND USAGE, with the choice between them a XOR. This is very sketchy). $\endgroup$
    – DoubleJay
    Commented Jun 4, 2010 at 5:56
  • $\begingroup$ It's not too hard to formulate overall - anyone with a little linear/integer programming background should be able to help with that. But definitely try to get an existing solver (though you definitely don't need a heavy-grade commercial one, unless your dataset is gigantic). $\endgroup$
    – DoubleJay
    Commented Jun 4, 2010 at 5:58
  • 3
    $\begingroup$ Perhaps people on stack overflow would be able to help you out on this one too? $\endgroup$
    – Robby McKilliam
    Commented Jun 4, 2010 at 5:59
  • $\begingroup$ The most affordable solver is GLPK which is free, but I'm not sure if it will run on your platform. For more possibilities check out the Linear Programming FAQ. faqs.org/faqs/linear-programming-faq CPLEX is the top-of-the-line package but it is expensive. Ten years ago when I had to decide which package our company should purchase, I remember being impressed with XPRESS-MP as being a somewhat more affordable but also very good system. CPLEX is an ILOG product (now IBM) and XPRESS-MP is a Dash Optimization product (now FICO). $\endgroup$
    – Timothy Chow
    Commented Jun 4, 2010 at 17:48
  • $\begingroup$ According to this web page (glpk-cli) there is a way to get GLPK (which does have a windows version) to interface with .NET: glpk-cli.sourceforge.net $\endgroup$
    – Victor Miller
    Commented Jun 4, 2010 at 20:06

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .