Friday, June 19, 2009

Solving a Linear Programming Problem

Operations Research (OR) is one of the key constituents of analytics. Solving a Linear Programming Problem (LPP) is core to OR. In one of my projects we have used a Simplex solver to choose an optimal solution from a set of available solutions. Its quite interesting to see a real life LPP.

We use the SYMPHONY an open source generic MILP (Mixed-Integer Linear Programs) solver from COIN-OR.

This solver takes two inputs

  • Problem model file: The Problem Model file contains the formulation of the LPP to be solved. The file uses GMPL (a subset of AMPL) a modeling language for Mathematical Programming.
  • Input data file:This file contains the input data of the problem to be solved.

Equipped with this information I decided to solve one of the 6th Semester Engineering LPP problems.(I still have my 6th Sem OR notes!!)

Problem Statement:
A small scale hardware production plant produces Nuts, Bolts and Rivets. A box of Nuts fetches a profit of Rs 20 per fortnight. Profit per fortnight from a box of Bolts and Rivets is Rs 6 and Rs 8 respectively. A box of Nuts requires 8 hrs of Milling, 2 hrs of lathe time and 4 hrs of threading time. A box of Bolts requires 2 hrs of Milling, and 4 hrs of threading time. A box of Rivets requires 3 hrs of milling and 1 hr of lathe time. Further milling, threading and lathe can operate 250 hrs, 150hrs and 50hrs per fortnight. Find an optimal solution to maximize the profit per fortnight of production plant.

Mathematical Formulation:
Lets formulate the problem to be solved. Let x1, x2, x3 represent the optimal quantities of production of the Nuts, Bolts and Rivets per fortnight.

The objective and constraints formulated can be easily derived from the problem statement.

Objective: Maximize 20 x1 + 6 x2 + 8 x3

Milling Constraints:
8 x1 + 2x2 + 3x3 <= 250

Threading Constraints:
4 x1 + 3x2 + 0x3 <= 150

Lathe Constraints:

2 x1 + 0x2 + 1x3 <= 50

Model File:

Now we have to represent our mathematical formulation in way the Symphony solver can understand. Following is the formulation of the same problem in GMPL format.

Filename: HardwarePlant.mod

/*Input Data we need to Solve*/

/* Input Set of products */
set products;

/* Gains of the product */
param gain{i in products};

/* Milling Requirements of the product */
param milling{i in products};

/* Lathe Requirements of the product */
param lathe{i in products};

/* Threading Requirements of the product */
param thread{i in products};

/* Milling Limit*/
param millingLimit;

/* Threading Limit*/
param threadLimit;

/* lathe Limit*/
param latheLimit;

/*Variable Declarations*/
var x{i in products}, >= 0;

maximize profit: sum{i in products} gain[i]*x[i];

subject to millingMachine: sum{i in products} milling[i]*x[i] <= millingLimit;

subject to latheMachine: sum{i in products} lathe[i]*x[i] <= latheLimit;

subject to threadMachine: sum{i in products} thread[i]*x[i] <= threadLimit;

At first we take as input a set of products. Then we need the gain for each of the products. Next, we need the milling, threading and lathe requirements for the product. We also need the limits for each of the machines. Thats all the input we need to find an optimal solution.

We define a variable set x representing the quantities of each of the product. We need to determine the values of x.

Further we define the objective and constraints to choose the optimal solution.

Input Data File:

Following is the input data file from our problem statement to be used with the model file.

Filename: HardwarePlant.dat


set products:= Nuts Bolts Rivets;

param gain:=Nuts 20
Bolts 6
Rivets 8 ;

param milling:=Nuts 8
Bolts 2
Rivets 3;

param thread:=Nuts 4
Bolts 3
Rivets 0;

param lathe:=Nuts 2
Bolts 0
Rivets 1;

param millingLimit := 250;
param threadLimit := 150;
param latheLimit := 50;


First we provide the input set of products. This can be strings representing the name of the products.Name of the product acts as an index for the rest of the parameters

Next we specify the gain per fortnight. From the model file its evident that we need gain for every product. We specify the name of the product and gain. As mentioned above the name serves as an index into the gain set.

We use the similar approach as above and specify the values for milling, threading and lathe requirements.

Finally, we specify the scalar values for the limits.

Using the model and input file, Symphony solver can be executed as follows

symphony -F HardwarePlant.mod -D HardwarePlant.dat

The execution produces the following output (only the relevant part shown)
Solution Cost: 700.000
Column names and values of nonzeros in the solution
x[Bolts] 50.000
x[Rivets] 50.000

Analyzing the output:
The solver is recommending for production of 50 bolts, 50 rivets and no nuts in a fortnight. And the optimal profit is Rs 700 per fortnight.
This is answer that matches the hand solved solution in my notes!!


Calvin said...

Sorry Srikanth..!!

Was away & "Lost" in some Stupid things..!!

THANKS for bringing me BACk ( to LIFE!) to something so Beautiful..!! :)

Will let u know AFTER me too solve it with something VERY VERY Special me discovered recently..purrhaps one of the GREATEST things i've discovered in my tiny life...!! :)

[Had not taken OR...but had studies Neural Networks dont have an idea..but it's about Maximizing &/or Minimizing some Function...w.r.t. some constraints...right..?]


Wait & Watch....! ;)

Shreenath M R said...

Hey good.
Incidentally, this problem has integer values as Optimal solution.

There are however cases where the Optimal solution gives 32.7 Trees, 654.45 men etc.

Does this Solver support Integer Programming Problem (IPP)?


Calvin said...

Yes !!!

Me did it...! :)

Solved 5 lines of commands..
(the 1'st being to define Profit, & the next 3 for each of the constraints, which I named as LatheConstraint, MillingConstraint & so on..!! So that makes it jusst a 1 line command..! :P)

And me *knew* that since "Mathematics is Blind", we could get solutions like -ve or fractional number of nuts & me had also specified that nuts >= 0, bolts >=0 & rivets >=0 & that EACH of them must belong to the Domain of INTEGERS..! :)

Annd Sure saw the Profit of 700 with the same values...! :)
{I guess, the solution is Unique...with a global maximum..?}

Gotta learn Latex, as you suggested...since it'd be even more b'ful to see variables like N-subScript-nuts,N-subScript-bolts,etc..!! :)

& Keep up the interesting work..! :)

Calvin said...

But me really curious to know HOW you people (like my other friends who learnt OR !) solved such problems by HAND...!?? :)


I used to hear that it involved lots of disciplined steps...n if u missed something down the line...the solution would be completely OFF the target..!?!?

Guess we need to use/employ our Computer-Cousins in SUCH cases..!

Calvin said...

Yes Srikanth..!

As Promised, here it is..! :)

Do lemme know..!:)