Want to improve this question? Update the question so it's on-topic for Stack Overflow.
Closed 5 years ago.
Can anyone recommend a library - free, or commercial but affordable (
There are some listed here:
http://en.wikipedia.org/wiki/Linear_programming#Solvers_and_scripting_.28programming.29_languages
....but I am just starting out with LP and hope someone can recommend something.
I am trying to basically minimize pricing for cell phone subscription services.
I guess the 1st question is: is linear programming even applicable to solving this problem?
A simplified example:
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
I have a set of detailed usage data for 50 users, and 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.
You can try Microsoft Solver Foundation. It is a mathematical programming library, which supports solving linear programming, mixed integer programming, stochastic programming, and other optimization and modeling problems.
It is available in Express (Free), Standard, and Enterprise (MSDN Subscriptions) editions.
First off, I'm guessing that you might need something more complex than a simple LP solver. Most cell phone services have breakpoints where you may want to switch from one service to another based on call length, frequency, time of day, etc. This switching implies the need for integer variables which means you might need a MILP (mixed integer linear programming) solver. (If all of your cost functions and constraints are convex, you could get by with an LP solver, but that's getting ahead of ourselves a little). The good news is that there are also open source and affordable MILP solvers out there as well.
I'd start with LP SOLVE or SYMPHONY. Check out the COIN-OR site here for some useful background info.
In response to your enhanced problem description, I think you could simply take each of the 50 users and cost out each plan then apply each of the options individually. With n users and m possible plans and p possible options, you need to look at m*p options for each user - but that's kind of boring.
A more interesting question from the user perspective is: Where are the break points between plans? Can you define indifference curves - combinations of usage where the user would be indifferent between two plans? This question could be address mathematically probably using some linear algebra techniques, but there's really not an objective function so it doesn't seem like a MILP.
Another interesting question from the provider perspective - how to set plans to maximize profits? Here you could apply some optimization if you take your 50 users to be representative of the population. You would need to put a cap on the total cost for a user and add costs to get profits, but I think a formulation is possible.
Check out the GNU Linear Programming Kit.
http://www.gnu.org/software/glpk/
