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
48
|
# 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_free_vars = num_vars
@num_basic_vars = num_inequalities
@total_vars = @num_free_vars + @num_basic_vars
@c = c.map { |flt| -1 * flt.rationalize } + Array.new(@num_basic_vars, 0)
@a = a.map.with_index { |ary, i|
if ary.size != @num_free_vars
raise ArgumentError, "a is inconsistent"
end
ary.map { |flt| flt.rationalize } +
Array.new(@num_basic_vars) { |ci| ci == i ? 1 : 0 }
}
@b = b.map { |flt| flt.rationalize }
@basic_vars = (@num_free_vars...@total_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
.get_params(maximize: nil, constraints: [], **kwargs) ⇒ Object
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
121
122
123
124
|
# File 'lib/compsci/simplex/parse.rb', line 89
def self.get_params(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
}
[c, a, b]
end
|
.maximize(expression, *ineqs) ⇒ Object
126
127
128
|
# File 'lib/compsci/simplex/parse.rb', line 126
def self.maximize(expression, *ineqs)
self.problem(maximize: expression, constraints: ineqs).solution
end
|
.problem(**kwargs) ⇒ Object
85
86
87
|
# File 'lib/compsci/simplex/parse.rb', line 85
def self.problem(**kwargs)
self.new(*self.get_params(**kwargs))
end
|
Instance Method Details
#can_improve? ⇒ Boolean
85
86
87
|
# File 'lib/compsci/simplex.rb', line 85
def can_improve?
!self.entering_variable.nil?
end
|
#current_solution ⇒ Object
81
82
83
|
# File 'lib/compsci/simplex.rb', line 81
def current_solution
@x[0...@num_free_vars]
end
|
#entering_variable ⇒ Object
idx of @c’s minimum negative value nil when no improvement is possible
92
93
94
|
# File 'lib/compsci/simplex.rb', line 92
def entering_variable
(0...@c.size).select { |i| @c[i] < 0 }.min_by { |i| @c[i] }
end
|
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
# File 'lib/compsci/simplex.rb', line 147
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
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
133
|
# File 'lib/compsci/simplex.rb', line 96
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_basic_vars.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
135
136
137
138
139
140
141
142
143
144
145
|
# File 'lib/compsci/simplex.rb', line 135
def pivot_row(column_ix)
min_ratio = nil
idx = nil
@num_basic_vars.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
67
68
69
70
|
# File 'lib/compsci/simplex.rb', line 67
def solution
self.solve
self.current_solution
end
|
#solve ⇒ Object
72
73
74
75
76
77
78
79
|
# File 'lib/compsci/simplex.rb', line 72
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
# File 'lib/compsci/simplex.rb', line 51
def update_solution
@x = Array.new(@total_vars, 0)
@basic_vars.each { |basic_var|
idx = nil
@num_basic_vars.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
|