bin/linear_programs/midatl

   1 #!/usr/bin/env python
   2
   3 """
   4 Solve an example problem with lp_solve.
   5 """
   6
   7 from math import acos, sin, cos
   8 import os
   9 import site
  10 import sys
  11
  12 # Basically, add '../src' to our path.
  13 # Needed for the imports that follow.
  14 site.addsitedir(os.path.dirname(os.path.abspath(sys.argv[0])) + '/../../src')
  15
  16 import LinearProgramming
  17
  18
  19 class Facility(object):
  20
  21     def __init__(self, fac_id, fac_capacity, fac_latitude, fac_longitude):
  22         self.id = fac_id
  23         self.capacity = fac_capacity
  24         self.latitude = fac_latitude
  25         self.longitude = fac_longitude
  26
  27     def distance(self, other_facility):
  28         return 3963.0 * acos(sin(self.latitude/57.2958) * sin(other_facility.latitude/57.2958) + cos(self.latitude/57.2958) * cos(other_facility.latitude/57.2958) *  cos(other_facility.longitude/57.2958 - self.longitude/57.2958))
  29
  30
  31 class Consumer(Facility):
  32     def __init__(self, fac_id, fac_capacity, fac_latitude, fac_longitude):
  33         super(Consumer, self).__init__(fac_id,
  34                                        fac_capacity,
  35                                        fac_latitude,
  36                                        fac_longitude)
  37
  38 class Producer(Facility):
  39     def __init__(self, fac_id, fac_capacity, fac_latitude, fac_longitude):
  40         super(Producer, self).__init__(fac_id,
  41                                        fac_capacity,
  42                                        fac_latitude,
  43                                        fac_longitude)
  44
  45 f = open('midatl.csv', 'r')
  46 f.readline() # Skip the header
  47
  48 producers = []
  49 consumers = []
  50
  51 for line in f:
  52     row = line.split(',')
  53     fac_id = int(row[0])
  54     fac_type = row[1]
  55     fac_capacity = float(row[2])
  56     fac_latitude = float(row[3])
  57     fac_longitude = float(row[4])
  58
  59     if fac_type == '"D"':
  60         c = Consumer(fac_id, fac_capacity, fac_latitude, fac_longitude)
  61         consumers.append(c)
  62     else:
  63         p = Producer(fac_id, fac_capacity, fac_latitude, fac_longitude)
  64         producers.append(p)
  65
  66
  67
  68 lp = LinearProgramming.LinearProgram()
  69
  70 # Loop through the consumer/producer pairs, calculating costs
  71 # (distances) and adding them to the array of objective function
  72 # coefficients.
  73 lp.objective_coefficients = []
  74
  75 for c_idx in range(0, len(consumers)):
  76     for p_idx in range(0, len(producers)):
  77         distance = consumers[c_idx].distance(producers[p_idx])
  78         lp.objective_coefficients.append(distance)
  79
  80
  81 num_cols = len(lp.objective_coefficients)
  82
  83 lp.constraint_matrix = []
  84 lp.inequalities = []
  85 lp.rhs = []
  86
  87 for c_idx in range(0, len(consumers)):
  88     demand = consumers[c_idx].capacity
  89     lp.rhs.append(demand)
  90
  91     lp.inequalities.append(LinearProgramming.GE)
  92
  93     demand_row = [0]*num_cols
  94     offset = c_idx * len(producers)
  95     for idx in range(0, len(producers)):
  96         demand_row[offset+idx] = 1
  97
  98     lp.constraint_matrix.append(demand_row)
  99
 100 for p_idx in range(0, len(producers)):
 101     supply = producers[p_idx].capacity
 102     lp.rhs.append(supply)
 103
 104     lp.inequalities.append(LinearProgramming.LE)
 105
 106     supply_row = [0]*num_cols
 107
 108     for idx in range(0,len(consumers)):
 109         offset = p_idx + len(producers)*idx
 110         supply_row[offset] = 1
 111     lp.constraint_matrix.append(supply_row)
 112
 113 lp.type = LinearProgramming.MINIMIZE
 114
 115 [v,x,duals] = lp.solve()
 116
 117 print 'Optimal objective function value: ', v
 118 print 'Optimal solution vector: ', x