From: Michael Orlitzky <michael@orlitzky.com>
Date: Sat, 22 May 2010 16:00:41 +0000 (-0400)
Subject: Added three LP scripts that run trials given uniformly-distributed cost coefficients.
X-Git-Url: http://gitweb.michael.orlitzky.com/?p=dead%2Fcensus-tools.git;a=commitdiff_plain;h=889eb060f21cd1fa55eb1217bb384d3e0d32c773

Added three LP scripts that run trials given uniformly-distributed cost coefficients.
---

diff --git a/bin/linear_programs/trials-uniform-large b/bin/linear_programs/trials-uniform-large
new file mode 100755
index 0000000..3b354e6
--- /dev/null
+++ b/bin/linear_programs/trials-uniform-large
@@ -0,0 +1,83 @@
+#!/usr/bin/env python
+
+"""
+Perform a series of trials given uniform distributions for the cost
+coefficients. Output the number of times each solution winds up being
+the optimal one.
+"""
+
+import os
+import random
+import site
+import sys
+
+# Basically, add '../src' to our path.
+# Needed for the imports that follow.
+site.addsitedir(os.path.dirname(os.path.abspath(sys.argv[0])) + '/../../src')
+
+import LinearProgramming
+import probability.Distribution
+
+# How many linear programs will we solve?
+NUM_TRIALS = 100000
+
+
+lp = LinearProgramming.LinearProgram()
+
+# We will say that the cost coefficients have the following means:
+#
+# c1 : 5
+# c2 : 100
+# c3 : 30
+# c4 : 10
+# c5 : 20
+# c6 : 300
+
+dist1 = probability.Distribution.Uniform(0, 10)
+dist2 = probability.Distribution.Uniform(0, 200)
+dist3 = probability.Distribution.Uniform(0, 60)
+dist4 = probability.Distribution.Uniform(0, 20)
+dist5 = probability.Distribution.Uniform(0, 40)
+dist6 = probability.Distribution.Uniform(0, 600)
+
+# We'll store all of the solution vectors and the number of times
+# that they have occurred in this hash.
+solutions = {}
+
+for idx in range(0, NUM_TRIALS):
+    c1 = dist1.sample()
+    c2 = dist2.sample()
+    c3 = dist3.sample()
+    c4 = dist4.sample()
+    c5 = dist5.sample()
+    c6 = dist6.sample()
+
+    lp.objective_coefficients = [c1, c2, c3, c4, c5, c6]
+    
+    lp.constraint_matrix = [ [1,1,1,0,0,0],
+                             [0,0,0,1,1,1],
+                             [1,0,0,1,0,0],
+                             [0,1,0,0,1,0],
+                             [0,0,1,0,0,1] ]
+
+    lp.inequalities = ([LinearProgramming.LE] * 2) + ([LinearProgramming.EQ] * 3)
+    
+    lp.rhs = [ 500, 600, 400, 300, 200 ]
+
+    [v,x,duals] = lp.solve()
+
+    # Implementation detail: lists can't serve as the key in a hash,
+    # so we just use the string representation of x.
+    solution_string = str(x)
+    
+    if solution_string in solutions:
+        solutions[solution_string] += 1
+    else:
+        solutions[solution_string] = 0
+
+
+print "Solution Vector : Count"
+print "-----------------------"
+
+for (key, value) in solutions.iteritems():
+    print key, ":", value
diff --git a/bin/linear_programs/trials-uniform-medium b/bin/linear_programs/trials-uniform-medium
new file mode 100755
index 0000000..626e9cc
--- /dev/null
+++ b/bin/linear_programs/trials-uniform-medium
@@ -0,0 +1,83 @@
+#!/usr/bin/env python
+
+"""
+Perform a series of trials given uniform distributions for the cost
+coefficients. Output the number of times each solution winds up being
+the optimal one.
+"""
+
+import os
+import random
+import site
+import sys
+
+# Basically, add '../src' to our path.
+# Needed for the imports that follow.
+site.addsitedir(os.path.dirname(os.path.abspath(sys.argv[0])) + '/../../src')
+
+import LinearProgramming
+import probability.Distribution
+
+# How many linear programs will we solve?
+NUM_TRIALS = 100000
+
+
+lp = LinearProgramming.LinearProgram()
+
+# We will say that the cost coefficients have the following means:
+#
+# c1 : 5
+# c2 : 100
+# c3 : 30
+# c4 : 10
+# c5 : 20
+# c6 : 300
+
+dist1 = probability.Distribution.Uniform(0, 10)
+dist2 = probability.Distribution.Uniform(25, 175)
+dist3 = probability.Distribution.Uniform(10, 50)
+dist4 = probability.Distribution.Uniform(0, 20)
+dist5 = probability.Distribution.Uniform(5, 35)
+dist6 = probability.Distribution.Uniform(50, 550)
+
+# We'll store all of the solution vectors and the number of times
+# that they have occurred in this hash.
+solutions = {}
+
+for idx in range(0, NUM_TRIALS):
+    c1 = dist1.sample()
+    c2 = dist2.sample()
+    c3 = dist3.sample()
+    c4 = dist4.sample()
+    c5 = dist5.sample()
+    c6 = dist6.sample()
+
+    lp.objective_coefficients = [c1, c2, c3, c4, c5, c6]
+    
+    lp.constraint_matrix = [ [1,1,1,0,0,0],
+                             [0,0,0,1,1,1],
+                             [1,0,0,1,0,0],
+                             [0,1,0,0,1,0],
+                             [0,0,1,0,0,1] ]
+
+    lp.inequalities = ([LinearProgramming.LE] * 2) + ([LinearProgramming.EQ] * 3)
+    
+    lp.rhs = [ 500, 600, 400, 300, 200 ]
+
+    [v,x,duals] = lp.solve()
+
+    # Implementation detail: lists can't serve as the key in a hash,
+    # so we just use the string representation of x.
+    solution_string = str(x)
+    
+    if solution_string in solutions:
+        solutions[solution_string] += 1
+    else:
+        solutions[solution_string] = 0
+
+
+print "Solution Vector : Count"
+print "-----------------------"
+
+for (key, value) in solutions.iteritems():
+    print key, ":", value
diff --git a/bin/linear_programs/trials-uniform-small b/bin/linear_programs/trials-uniform-small
new file mode 100755
index 0000000..2558702
--- /dev/null
+++ b/bin/linear_programs/trials-uniform-small
@@ -0,0 +1,83 @@
+#!/usr/bin/env python
+
+"""
+Perform a series of trials given uniform distributions for the cost
+coefficients. Output the number of times each solution winds up being
+the optimal one.
+"""
+
+import os
+import random
+import site
+import sys
+
+# Basically, add '../src' to our path.
+# Needed for the imports that follow.
+site.addsitedir(os.path.dirname(os.path.abspath(sys.argv[0])) + '/../../src')
+
+import LinearProgramming
+import probability.Distribution
+
+# How many linear programs will we solve?
+NUM_TRIALS = 100000
+
+
+lp = LinearProgramming.LinearProgram()
+
+# We will say that the cost coefficients have the following means:
+#
+# c1 : 5
+# c2 : 100
+# c3 : 30
+# c4 : 10
+# c5 : 20
+# c6 : 300
+
+dist1 = probability.Distribution.Uniform(0, 10)
+dist2 = probability.Distribution.Uniform(75, 125)
+dist3 = probability.Distribution.Uniform(20, 40)
+dist4 = probability.Distribution.Uniform(0, 20)
+dist5 = probability.Distribution.Uniform(10, 30)
+dist6 = probability.Distribution.Uniform(200, 400)
+
+# We'll store all of the solution vectors and the number of times
+# that they have occurred in this hash.
+solutions = {}
+
+for idx in range(0, NUM_TRIALS):
+    c1 = dist1.sample()
+    c2 = dist2.sample()
+    c3 = dist3.sample()
+    c4 = dist4.sample()
+    c5 = dist5.sample()
+    c6 = dist6.sample()
+
+    lp.objective_coefficients = [c1, c2, c3, c4, c5, c6]
+    
+    lp.constraint_matrix = [ [1,1,1,0,0,0],
+                             [0,0,0,1,1,1],
+                             [1,0,0,1,0,0],
+                             [0,1,0,0,1,0],
+                             [0,0,1,0,0,1] ]
+
+    lp.inequalities = ([LinearProgramming.LE] * 2) + ([LinearProgramming.EQ] * 3)
+    
+    lp.rhs = [ 500, 600, 400, 300, 200 ]
+
+    [v,x,duals] = lp.solve()
+
+    # Implementation detail: lists can't serve as the key in a hash,
+    # so we just use the string representation of x.
+    solution_string = str(x)
+    
+    if solution_string in solutions:
+        solutions[solution_string] += 1
+    else:
+        solutions[solution_string] = 0
+
+
+print "Solution Vector : Count"
+print "-----------------------"
+
+for (key, value) in solutions.iteritems():
+    print key, ":", value