Class: Simplex

Inherits:
Object
  • Object
show all
Defined in:
lib/simplex.rb

Defined Under Namespace

Classes: UnboundedProblem

Constant Summary collapse

DEFAULT_MAX_PIVOTS = 
10_000

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(c, a, b) ⇒ Simplex

Returns a new instance of Simplex.



15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
# File 'lib/simplex.rb', line 15

def initialize(c, a, b)
  @pivot_count = 0
  @max_pivots = DEFAULT_MAX_PIVOTS

  # Problem dimensions
  @num_non_slack_vars = a.first.length
  @num_constraints    = b.length
  @num_vars           = @num_non_slack_vars + @num_constraints

  # Set up initial matrix A and vectors b, c
  @c = Vector[*c.map {|c1| -1*c1 } + [0]*@num_constraints]
  @a = a.map {|a1| Vector[*(a1.clone + [0]*@num_constraints)]}
  @b = Vector[*b.clone]

  unless @a.all? {|a| a.size == @c.size } and @b.size == @a.length
    raise ArgumentError, "Input arrays have mismatched dimensions" 
  end

  0.upto(@num_constraints - 1) {|i| @a[i][@num_non_slack_vars + i] = 1 }

  # set initial solution: all non-slack variables = 0
  @x          = Vector[*([0]*@num_vars)]
  @basic_vars = (@num_non_slack_vars...@num_vars).to_a
  update_solution
end

Instance Attribute Details

#max_pivots ⇒ Object

Returns the value of attribute max_pivots.



13
14
15
 
# File 'lib/simplex.rb', line 13

def max_pivots
  @max_pivots
end

Instance Method Details

#assert(boolean) ⇒ Object 



187
188
189
 
# File 'lib/simplex.rb', line 187

def assert(boolean)
  raise unless boolean
end

#basic_variable_in_row(pivot_row) ⇒ Object 



129
130
131
132
133
 
# File 'lib/simplex.rb', line 129

def basic_variable_in_row(pivot_row)
  column_indices.detect do |column_ix|
    @a[pivot_row][column_ix] == 1 and @basic_vars.include?(column_ix)
  end
end

#can_improve? ⇒ Boolean

Returns:



69
70
71
 
# File 'lib/simplex.rb', line 69

def can_improve?
  !!entering_variable
end

#column_indices ⇒ Object 



139
140
141
 
# File 'lib/simplex.rb', line 139

def column_indices
  (0...@a.first.size).to_a
end

#current_solution ⇒ Object 



46
47
48
 
# File 'lib/simplex.rb', line 46

def current_solution
  @x.to_a[0...@num_non_slack_vars]
end

#entering_variable ⇒ Object 



77
78
79
80
 
# File 'lib/simplex.rb', line 77

def entering_variable
  variables.select { |var| @c[var] < 0 }.
            min_by { |var| @c[var] }
end

#formatted_tableau ⇒ Object 



143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
 
# File 'lib/simplex.rb', line 143

def formatted_tableau
  if can_improve?
    pivot_column = entering_variable
    pivot_row    = pivot_row(pivot_column)
  else
    pivot_row = nil
  end
  num_cols = @c.size + 1
  c = formatted_values(@c.to_a)
  b = formatted_values(@b.to_a)
  a = @a.to_a.map {|ar| formatted_values(ar.to_a) }
  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 {|c| c.rjust(max, " ") }
  a.zip(b) do |arow, brow|
    result << (arow + [brow]).map {|a| a.rjust(max, " ") }
    result.last.insert(arow.length, "|")
  end
  lines = result.map {|b| b.join("  ") }
  max_line_length = lines.map(&:length).max
  lines.insert(1, "-"*max_line_length)
  lines.join("\n")
end

#formatted_values(array) ⇒ Object 



170
171
172
 
# File 'lib/simplex.rb', line 170

def formatted_values(array)
  array.map {|c| "%2.3f" % c }
end

#last_min_by(array) ⇒ Object

like Enumerable#min_by except if multiple values are minimum it returns the last



176
177
178
179
180
181
182
183
184
185
 
# File 'lib/simplex.rb', line 176

def last_min_by(array)
  best_element, best_value = nil, nil
  array.each do |element|
    value = yield element
    if !best_element || value <= best_value
      best_element, best_value = element, value
    end
  end
  best_element
end

#pivot ⇒ Object

Raises:



82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
 
# File 'lib/simplex.rb', line 82

def pivot
  pivot_column = entering_variable
  pivot_row    = pivot_row(pivot_column)
  raise UnboundedProblem unless pivot_row
  leaving_var  = basic_variable_in_row(pivot_row)
  replace_basic_variable(leaving_var => pivot_column)

  pivot_ratio = Rational(1, @a[pivot_row][pivot_column])

  # update pivot row
  @a[pivot_row] *= pivot_ratio
  @b[pivot_row] = pivot_ratio * @b[pivot_row]

  # update objective
  @c -= @c[pivot_column] * @a[pivot_row]

  # update A and B
  (row_indices - [pivot_row]).each do |row_ix|
    r = @a[row_ix][pivot_column]
    @a[row_ix] -= r * @a[pivot_row]
    @b[row_ix] -= r * @b[pivot_row]
  end

  update_solution
end

#pivot_row(column_ix) ⇒ Object 



115
116
117
118
119
120
121
122
123
124
125
126
127
 
# File 'lib/simplex.rb', line 115

def pivot_row(column_ix)
  row_ix_a_and_b = row_indices.map { |row_ix|
    [row_ix, @a[row_ix][column_ix], @b[row_ix]]
  }.reject { |_, a, b|
    a == 0
  }.reject { |_, a, b|
    (b < 0) ^ (a < 0) # negative sign check
  }
  row_ix, _, _ = *last_min_by(row_ix_a_and_b) { |_, a, b|
    Rational(b, a)
  }
  row_ix
end

#replace_basic_variable(hash) ⇒ Object 



108
109
110
111
112
113
 
# File 'lib/simplex.rb', line 108

def replace_basic_variable(hash)
  from, to = hash.keys.first, hash.values.first
  @basic_vars.delete(from)
  @basic_vars << to
  @basic_vars.sort!
end

#row_indices ⇒ Object 



135
136
137
 
# File 'lib/simplex.rb', line 135

def row_indices
  (0...@a.length).to_a
end

#solution ⇒ Object 



41
42
43
44
 
# File 'lib/simplex.rb', line 41

def solution
  solve
  current_solution
end

#solve ⇒ Object 



61
62
63
64
65
66
67
 
# File 'lib/simplex.rb', line 61

def solve
  while can_improve?
    @pivot_count += 1
    raise "Too many pivots" if @pivot_count > max_pivots 
    pivot
  end
end

#update_solution ⇒ Object 



50
51
52
53
54
55
56
57
58
59
 
# File 'lib/simplex.rb', line 50

def update_solution
  0.upto(@num_vars - 1) {|i| @x[i] = 0 }

  @basic_vars.each do |basic_var|
    row_with_1 = row_indices.detect do |row_ix|
      @a[row_ix][basic_var] == 1
    end
    @x[basic_var] = @b[row_with_1]
  end
end

#variables ⇒ Object 



73
74
75
 
# File 'lib/simplex.rb', line 73

def variables
  (0...@c.size).to_a
end