# Operation Research

## Linear Programming

Linear programming (LP, also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in amathematical modelwhose requirements are represented bylinear relationships. Linear programming is a special case of mathematical programming (also known asmathematical optimization).

Linear programming (LP) is a powerful framework for describing and solving optimization problems. It allows you to specify a set of decision variables, and a linear objective and a set of linear constraints on these variables. To give a simple and widely used example, consider the problem of minimizing the cost of a selection of foods that meets all the recommended daily nutrient guidelines. The LP model would have a set of decision variables that capture the amount of each food to buy, a linear objective that minimizes the total cost of purchasing the chosen foods, and a linear constraint for each nutrient, requiring that the chosen foods together contain a sufficient quantity of that nutrient. Using linear algebra notation, a linear program can be described as follows:

Objective: minimize c^(T) x

Constraints: A x = b (linear constraints)

l <= x <= u (bound constraints)

When described in this form, the vector x represents the decision variables, the vector c captures the linear objective function, the matrix equation Ax = b specifies the linear constraints on x, and the vectors l and u give the lower and upper bounds on x. The set of applications of linear programming is literally too long to list. It includes everything from production scheduling to web advertising optimization to clothing manufacturing. LP touches nearly every commercial industry in some way.

## Demonstration with an example

We represent the small nation of Pacific Paradise where we have been working to improve our response to the devastating cyclones that are forecast for the coming season. We would like your assistance in planning our disaster relief distribution strategy (DRDS).We have modeled our distribution network using three types of nodes: the central disaster relief depot (CDRD); the forward supply depots (FSD); and the disaster demand points (DDP). Our plan is to transport relief goods from the CDRD to the five FSDs prior to a disaster. This will mean that the relief goods will be closer to where they are needed, but also means that if one or more of the depots are destroyed in the cyclone then other depots can be used for supply. Relief goods cost us 145 per tonne. We have estimated the cost of transporting one tonne of relief goods from the CDRD to each of five FSDs and FSDs to 10 DDPs.

In the event of a cyclone, we estimate demands (tonnes) at each of the disasters. Weve also realized that this plan will not work for us since we have a maximum capacity at each FSD of 790 tonnes. It is good that we will now be able to fit the supplies in our FSDs. However, were concerned that some of the DDPs are too reliant on specific FSDs. Were now thinking it would be safer to make sure that no more than half of the demand at each DDP is coming from a single FSD. We have received some advice from our weather bureau outlining possible scenarios for the path of Cyclone Cyril. For example, they have told us that there is a 10% chance that the path it takes will pass over FSDs 0 and 3, destroying any relief goods we had moved there.

**SETS**

I set of FSDs depots

J set of DDPs depots

S set of scenarios

**DATA**

cost_cdrd_fsd_{i} cost of transport from cdrd to fsd for i in I

cost_fsd_ddp_{ij} cost of transport from fsd for i in I to ddp for j in J

relief_good_cost cost of relief goods

demand_{j} demand at ddp node for j in J

maximum_capacity maximum capacity limit

scenario_probability_{s} probability of scenarios for s in S

FSDs_destroyed_{s} FSDs destroyed in scenario for s in S

**VARIABLES**

C_F_{i} Amount of supplies to move from CDRD to FSD for i in I

F_D_{ijs} Amount of supplies to move from FSD for i in I to DDP for j in J

**OBJECTIVE FUNCTION**

Minimizesum(cost_cdrd_fsd_{i} + relief_good_cost) * C_F_{i} +sumcost_fsd_ddp_{ij} * scenario_probability_{s} * F_D_{ijs}

**CONSTRAINTS**

- The Sum of demand at the DDP should equal FSD nodes for every FSD node and scenarios.

sumF_D_{ijs} = C_F_{i} for every i in I, for every s in S

- Capacity at each FSD node should not cross the maximum capacity

C_F_{i} <= maximum_capacity for every i in I

- The Sum of the amount of supplies to move from FSD nodes should be greater than the demand at each DDP node in each scenario.

sumF_D_{ijs} >= demand_{j} for every j in J, for every s in S

- At least half the demand should be coming from the FSD nodes.

F_D_{ijs} <= demand_{j} * 1/2 for i in I, for j in J, for s in S

- The DDP nodes should be equal to 0 if the scenario is in FSDs_destroyed for every FSD, DDP, scenarios.

F_D_{ijs} = 0 for j in J, for i in I, for s in S | if i in FSDs_destroyed[s]

- And lastly the non-negativity constraints

C_F_{i}, F_D_{ijs} >= 0, for i in I, for j in J, for s in S

TheGurobiOptimizer is a commercial optimization solver for linear programming (LP), quadratic programming (QP), quadratically constrained programming (QCP), mixed integer linear programming (MILP), mixed-integer quadratic programming (MIQP), and mixed-integer quadratically constrained programming (MIQCP).

Gurobi Optimizer is one of the fastest solvers until now. The license fee of Gurobi optimizer is quite expensive though. If you have an educational email, you can get a license till the end of your educational email validity.

**Full Code:**

#!/usr/bin/env python3 # -*- coding: utf-8 -*- """ Created on Wed Mar 11 12:21:12 2020 @author: Pritish Roy """ from gurobipy import * # Sets I = range(0, 5) J = range(0, 10) S = range(0, 6) # Data demand = [112, 254, 117, 272, 135, 125, 133, 223, 257, 201] Cost_CDRD_FSD = [91, 71, 94, 52, 30] Cost_FSD_DDP = [ [50, 46, 35, 85, 151, 98, 140, 54, 31, 121], [67, 57, 42, 79, 144, 90, 132, 54, 50, 115], [70, 67, 57, 103, 168, 115, 157, 74, 48, 139], [74, 56, 41, 37, 98, 45, 86, 31, 70, 71], [100, 81, 67, 47, 94, 47, 80, 55, 95, 72] ] relief_good_cost = 145 maximum_capacity = 790 scenario_probability = [0.10, 0.09, 0.13, 0.18, 0.24, 0.26] FSDs_destroyed = [ [0, 3], [0, 1], [1, 2], [3], [1, 4], [2] ] ######################################################## # Model m = Model("Pacific Paradise") # Variables CDRD_FSD = {} FSD_DDP = {} for i in I: for j in J: for s in S: CDRD_FSD[i] = m.addVar() FSD_DDP[i, j, s] = m.addVar() # Objective m.setObjective( quicksum( (Cost_CDRD_FSD[i] + relief_good_cost) * CDRD_FSD[i] for i in I ) + quicksum( Cost_FSD_DDP[i][j] * FSD_DDP[i, j, s] * scenario_probability[s] for i in I for j in J for s in S ), GRB.MINIMIZE ) # Set constraints for i in I: m.addConstr(CDRD_FSD[i] <= maximum_capacity) for s in S: m.addConstr( quicksum(FSD_DDP[i, j, s] for j in J) <= CDRD_FSD[i] ) for j in J: for s in S: m.addConstr(quicksum( FSD_DDP[i, j, s] for i in I) == demand[j] ) for i in I: m.addConstr(FSD_DDP[i, j, s] <= 1 / 2 * demand[j]) for j in J: for i in I: for s in S: if i in FSDs_destroyed[s]: m.addConstr( FSD_DDP[i, j, s] == 0 ) # Optimize m.optimize() # Answer print(f'Optimal cost of Transport + Purchase: {m.objVal}') print('CDRD ----> FSD') for i in I: print(f"{i} ---- {[round(CDRD_FSD[i].x, 1)]}") print('--------------------------------------------------') print('\t\t\tFSD ----> DDP') for i in I: print(f"{i} ---- {[round(FSD_DDP[i, j, s].x, 1) for j in J]}")

**OUTPUT**

Optimal cost of Transport + Purchase: 716436.7299999997 CDRD ----> FSD 0 ---- [249.0] 1 ---- [249.0] 2 ---- [790.0] 3 ---- [790.0] 4 ---- [790.0] -------------------------------------------------- FSD ----> DDP 0 ---- [56.0, 64.5, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 128.5, 0.0] 1 ---- [0.0, 62.5, 58.5, 0.0, 0.0, 0.0, 0.0, 0.0, 128.0, 0.0] 2 ---- [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0] 3 ---- [56.0, 127.0, 58.5, 136.0, 67.5, 62.5, 66.5, 111.5, 0.5, 100.5] 4 ---- [0.0, 0.0, 0.0, 136.0, 67.5, 62.5, 66.5, 111.5, 0.0, 100.5]