bin/linear_programs/trials-uniform-large

   1 #!/usr/bin/env python
   2
   3 """
   4 Perform a series of trials given uniform distributions for the cost
   5 coefficients. Output the number of times each solution winds up being
   6 the optimal one.
   7 """
   8
   9 import os
  10 import random
  11 import site
  12 import sys
  13
  14 # Basically, add '../src' to our path.
  15 # Needed for the imports that follow.
  16 site.addsitedir(os.path.dirname(os.path.abspath(sys.argv[0])) + '/../../src')
  17
  18 import LinearProgramming
  19 import probability.Distribution
  20
  21 # How many linear programs will we solve?
  22 NUM_TRIALS = 100000
  23
  24
  25 lp = LinearProgramming.LinearProgram()
  26
  27 # We will say that the cost coefficients have the following means:
  28 #
  29 # c1 : 5
  30 # c2 : 100
  31 # c3 : 30
  32 # c4 : 10
  33 # c5 : 20
  34 # c6 : 300
  35
  36 dist1 = probability.Distribution.Uniform(0, 10)
  37 dist2 = probability.Distribution.Uniform(0, 200)
  38 dist3 = probability.Distribution.Uniform(0, 60)
  39 dist4 = probability.Distribution.Uniform(0, 20)
  40 dist5 = probability.Distribution.Uniform(0, 40)
  41 dist6 = probability.Distribution.Uniform(0, 600)
  42
  43 # We'll store all of the solution vectors and the number of times
  44 # that they have occurred in this hash.
  45 solutions = {}
  46
  47 for idx in range(0, NUM_TRIALS):
  48     c1 = dist1.sample()
  49     c2 = dist2.sample()
  50     c3 = dist3.sample()
  51     c4 = dist4.sample()
  52     c5 = dist5.sample()
  53     c6 = dist6.sample()
  54
  55     lp.objective_coefficients = [c1, c2, c3, c4, c5, c6]
  56
  57     lp.constraint_matrix = [ [1,1,1,0,0,0],
  58                              [0,0,0,1,1,1],
  59                              [1,0,0,1,0,0],
  60                              [0,1,0,0,1,0],
  61                              [0,0,1,0,0,1] ]
  62
  63     lp.inequalities = ([LinearProgramming.LE] * 2) + ([LinearProgramming.EQ] * 3)
  64
  65     lp.rhs = [ 500, 600, 400, 300, 200 ]
  66
  67     [v,x,duals] = lp.solve()
  68
  69     # Implementation detail: lists can't serve as the key in a hash,
  70     # so we just use the string representation of x.
  71     solution_string = str(x)
  72
  73     if solution_string in solutions:
  74         solutions[solution_string] += 1
  75     else:
  76         solutions[solution_string] = 1
  77
  78
  79 print "Solution Vector : Count"
  80 print "-----------------------"
  81
  82 for (key, value) in solutions.iteritems():
  83     print key, ":", value