Class: CompSci::Simplex
- Inherits:
-
Object
show all
- Defined in:
- lib/compsci/simplex.rb,
lib/compsci/simplex/parse.rb
Defined Under Namespace
Modules: Parse
Classes: Error, SanityCheck, TooManyPivots, UnboundedProblem
Constant Summary
collapse
- DEFAULT_MAX_PIVOTS =
10_000
Instance Attribute Summary collapse
Class Method Summary
collapse
Instance Method Summary
collapse
Constructor Details
#initialize(c, a, b) ⇒ Simplex
c - coefficients of objective function; size: num_vars a - inequality lhs coefficients; 2dim size: num_inequalities, num_vars b - inequality rhs constants size: num_inequalities
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
# File 'lib/compsci/simplex.rb', line 20
def initialize(c, a, b)
num_vars = c.size
num_inequalities = b.size
raise(ArgumentError, "a doesn't match b") unless a.size == num_inequalities
raise(ArgumentError, "a doesn't match c") unless a.first.size == num_vars
@max_pivots = DEFAULT_MAX_PIVOTS
@num_non_slack_vars = num_vars
@num_constraints = num_inequalities
@num_vars = @num_non_slack_vars + @num_constraints
@c = c.map { |flt| -1 * flt } + Array.new(@num_constraints, 0)
@a = a.map.with_index { |ary, i|
if ary.size != @num_non_slack_vars
raise ArgumentError, "a is inconsistent"
end
ary + Array.new(@num_constraints) { |ci| ci == i ? 1 : 0 }
}
@b = b
@basic_vars = (@num_non_slack_vars...@num_vars).to_a
self.update_solution
end
|
Instance Attribute Details
#max_pivots ⇒ Object
Returns the value of attribute max_pivots.
15
16
17
|
# File 'lib/compsci/simplex.rb', line 15
def max_pivots
@max_pivots
end
|
Class Method Details
.maximize(expression, *ineqs) ⇒ Object
122
123
124
|
# File 'lib/compsci/simplex/parse.rb', line 122
def self.maximize(expression, *ineqs)
self.problem(maximize: expression, constraints: ineqs).solution
end
|
.problem(maximize: nil, constraints: [], **kwargs) ⇒ Object
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
# File 'lib/compsci/simplex/parse.rb', line 85
def self.problem(maximize: nil, constraints: [], **kwargs)
if maximize
expr, maximize = maximize, true
elsif kwargs[:minimize]
expr, maximize = kwargs[:minimize], false
else
raise(ArgumentError, "one of maximize/minimize expected")
end
unless expr.is_a?(String)
raise(ArgumentError, "bad expr: #{expr} (#{expr.class})")
end
obj_cof = Parse.expression(expr)
c = [] a = [] b = []
letter_vars = obj_cof.keys
letter_vars.each { |v| c << obj_cof[v] }
constraints.each { |str|
unless str.is_a?(String)
raise(ArgumentError, "bad constraint: #{str} (#{str.class})")
end
cofs = []
ineq_cofs, rhs = Parse.inequality(str)
letter_vars.each { |v|
raise("constraint #{str} is missing var #{v}") unless ineq_cofs.key?(v)
cofs << ineq_cofs[v]
}
a.push cofs
b.push rhs
}
self.new(c, a, b)
end
|
Instance Method Details
#can_improve? ⇒ Boolean
84
85
86
|
# File 'lib/compsci/simplex.rb', line 84
def can_improve?
!self.entering_variable.nil?
end
|
#current_solution ⇒ Object
80
81
82
|
# File 'lib/compsci/simplex.rb', line 80
def current_solution
@x[0...@num_non_slack_vars]
end
|
#entering_variable ⇒ Object
idx of @c’s minimum negative value nil when no improvement is possible
91
92
93
|
# File 'lib/compsci/simplex.rb', line 91
def entering_variable
(0...@c.size).select { |i| @c[i] < 0 }.min_by { |i| @c[i] }
end
|
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
|
# File 'lib/compsci/simplex.rb', line 146
def formatted_tableau
if self.can_improve?
pivot_column = self.entering_variable
pivot_row = self.pivot_row(pivot_column)
else
pivot_row = nil
end
c = @c.to_a.map { |flt| "%2.3f" % flt }
b = @b.to_a.map { |flt| "%2.3f" % flt }
a = @a.to_a.map { |vec| vec.to_a.map { |flt| "%2.3f" % flt } }
if pivot_row
a[pivot_row][pivot_column] = "*" + a[pivot_row][pivot_column]
end
max = (c + b + a + ["1234567"]).flatten.map(&:size).max
result = []
result << c.map { |str| str.rjust(max, " ") }
a.zip(b) do |arow, brow|
result << (arow + [brow]).map { |val| val.rjust(max, " ") }
result.last.insert(arow.length, "|")
end
lines = result.map { |ary| ary.join(" ") }
max_line_length = lines.map(&:length).max
lines.insert(1, "-"*max_line_length)
lines.join("\n")
end
|
#pivot ⇒ Object
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
# File 'lib/compsci/simplex.rb', line 95
def pivot
pivot_column = self.entering_variable or return nil
pivot_row = self.pivot_row(pivot_column) or raise UnboundedProblem
leaving_var = nil
@a[pivot_row].each_with_index { |a, i|
if a == 1 and @basic_vars.include?(i)
leaving_var = i
break
end
}
raise(SanityCheck, "no leaving_var") if leaving_var.nil?
@basic_vars.delete(leaving_var)
@basic_vars.push(pivot_column)
@basic_vars.sort!
pivot_ratio = Rational(1, @a[pivot_row][pivot_column])
@a[pivot_row] = @a[pivot_row].map { |val| val * pivot_ratio }
@b[pivot_row] = @b[pivot_row] * pivot_ratio
@c = @c.map.with_index { |val, i|
val - @c[pivot_column] * @a[pivot_row][i]
}
@num_constraints.times { |i|
next if i == pivot_row
r = @a[i][pivot_column]
@a[i] = @a[i].map.with_index { |val, j| val - r * @a[pivot_row][j] }
@b[i] = @b[i] - r * @b[pivot_row]
}
self.update_solution
end
|
#pivot_row(column_ix) ⇒ Object
134
135
136
137
138
139
140
141
142
143
144
|
# File 'lib/compsci/simplex.rb', line 134
def pivot_row(column_ix)
min_ratio = nil
idx = nil
@num_constraints.times { |i|
a, b = @a[i][column_ix], @b[i]
next if a == 0 or (b < 0) ^ (a < 0)
ratio = Rational(b, a)
idx, min_ratio = i, ratio if min_ratio.nil? or ratio <= min_ratio
}
idx
end
|
#solution ⇒ Object
66
67
68
69
|
# File 'lib/compsci/simplex.rb', line 66
def solution
self.solve
self.current_solution
end
|
#solve ⇒ Object
71
72
73
74
75
76
77
78
|
# File 'lib/compsci/simplex.rb', line 71
def solve
count = 0
while self.can_improve?
count += 1
raise(TooManyPivots, count.to_s) unless count < @max_pivots
self.pivot
end
end
|
#update_solution ⇒ Object
does not modify vector / matrix
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
# File 'lib/compsci/simplex.rb', line 50
def update_solution
@x = Array.new(@num_vars, 0)
@basic_vars.each { |basic_var|
idx = nil
@num_constraints.times { |i|
if @a[i][basic_var] == 1
idx =i
break
end
}
raise(SanityCheck, "no idx for basic_var #{basic_var} in a") unless idx
@x[basic_var] = @b[idx]
}
end
|