Distribution network linear programming constraints

Question

I'm trying to write a linear program in Python with the Pulp framework - donation clinics provide blood which is sent to a distribution center, and the onto a hospital for use. The difficulty is in creating constraints to decide whether a distribution center is used or not and preserving flow from what is entering the DC to what is exiting?

# Import PuLP modeler functions
from pulp import *

# Creates a list of all the supply nodes
Clinics = ["San Francisco",
      "Los Angeles",
      "Phoenix",
      "Denver"]
# Creates a list of all demand nodes
Hospitals = ["San Diego",
      "Miami",
      "Tucson",
      "Dallas"]

#Creates list of all transshipment nodes
Dist = ["NYC",
    "Boston"]

# Creates a dictionary for the number of units of supply at each clinic c
supplyData = {#Clinic     Supply
      "San Francisco":17,
      "Los Angeles"  :20,
      "Phoenix"      :17,
      "Denver"       :20,
      }


# Creates a dictionary for the number of units of demand at each hospital h
demand = { #Hospital    Demand
      "San Diego":17,
      "Miami"  :10,
      "Tucson"   :15,
      "Dallas"   :12
      }

# Creates a dictionary the fixed cost of running each dist centre
dcCost = { #Dist       Min Flow Fixed Cost
      "NYC":      [0,700],
      "Boston":   [0,700],
      }

# Creates a list of costs for each transportation path
costsCDC = [  #Dist
     #NY BO
     [5, 3], #SF
     [4, 7], #LA    Clinics
     [6, 5], #PH
     [9, 8]  #DE
     ]

costsDCH =  [  #Hospitals
     #SD MI TU DA
     [5, 3, 2, 6], #NY
     [4, 7, 8, 10] #BO    Dist
     ]

# Creates a list of tuples containing all the possible routes
Routes = [(c,dc) for c in Clinics for dc in Dist]
Routes2 = [(dc,h) for dc in Dist for h in Hospitals]

# Splits the dictionaries
(minCap,fixedCost) = splitDict(dcCost)

# The cost data is made into a dictionary
costs = makeDict([Clinics,Dist],costsCDC,0)
costs2 = makeDict([Dist, Hospitals], costsDCH,0)
# Creates the problem variables of the Flow on the Arcs
flow = LpVariable.dicts("Route",(Clinics,Dist),0,None,LpInteger)
flow2 = LpVariable.dicts("Route2",(Dist,Hospitals),0,None,LpInteger)

# Creates the master problem variables of whether to build the DC or not
build = LpVariable.dicts("BuildDC",Dist,0,1,LpInteger)

# Creates the 'prob' variable to contain the problem data
prob = LpProblem("Test Problem",LpMinimize)

# The objective function is added to prob - The sum of the transportation costs (c -> dc; dc -> h) and the DC fixed costs
prob += lpSum([flow[c][dc]*costs[c][dc] for (c,dc) in Routes])+lpSum([fixedCost[dc]*build[dc] for dc in Dist]) +lpSum([flow2[dc][h]*costs2[dc][h] for (dc,h) in Routes2]),"Total Costs"

# The Supply maximum constraints are added for each supply node (clinics)
for c in Clinics:
    prob += lpSum([flow[c][dc] for dc in Dist])>=supplyData[c], "Sum of units out of Clinic %s"%c

# The Demand minimum constraints are added for each demand node (hospital)
for h in Hospitals:
    prob += lpSum([flow2[dc][h] for dc in Dist])>=demand[h], "Sum of units into Hospitals %s"%h

Erwin Kalvelagen · Accepted Answer · 2015-12-04 05:42:24Z

1

This is usually handled by constraints like: if dc is closed then all flows to and from dc should be zero. E.g. flow[i,dc]<=IsOpen[dc]*MaxFlow[i,dc] where IsOpen is a binary variable and MaxFlow is a constant. (Similar for flow[dc,j]).

answered Dec 4, 2015 at 5:42

Erwin Kalvelagen

16.9k3 gold badges17 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Distribution network linear programming constraints

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related