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 x₁, x₂, x₃ 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 x₁ + 6 x₂ + 8 x₃

Milling Constraints:
8 x₁ + 2x₂ + 3x₃ <= 250

Threading Constraints:
4 x₁ + 3x₂ + 0x₃ <= 150

Lathe Constraints:
2 x₁ + 0x₂ + 1x₃ <= 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;

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

/*Constraints*/
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;  

end;  

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

data;

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;

end;

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.

Execution:
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!!