Class: Cassowary::SimplexSolver

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

Constant Summary collapse

Epsilon = 
1.0e-8

Instance Attribute Summary collapse

Instance Method Summary collapse

Instance Attribute Details

#auto_solve ⇒ Object

Returns the value of attribute auto_solve.



8
9
10
 
# File 'lib/simplex_solver.rb', line 8

def auto_solve
  @auto_solve
end

#columns ⇒ Object

Returns the value of attribute columns.



8
9
10
 
# File 'lib/simplex_solver.rb', line 8

def columns
  @columns
end

#edit_constraints ⇒ Object

Returns the value of attribute edit_constraints.



8
9
10
 
# File 'lib/simplex_solver.rb', line 8

def edit_constraints
  @edit_constraints
end

#edit_minus_error_vars ⇒ Object

Returns the value of attribute edit_minus_error_vars.



8
9
10
 
# File 'lib/simplex_solver.rb', line 8

def edit_minus_error_vars
  @edit_minus_error_vars
end

#edit_plus_error_vars ⇒ Object

Returns the value of attribute edit_plus_error_vars.



8
9
10
 
# File 'lib/simplex_solver.rb', line 8

def edit_plus_error_vars
  @edit_plus_error_vars
end

#edit_vars ⇒ Object

Returns the value of attribute edit_vars.



8
9
10
 
# File 'lib/simplex_solver.rb', line 8

def edit_vars
  @edit_vars
end

#error_vars ⇒ Object

Returns the value of attribute error_vars.



8
9
10
 
# File 'lib/simplex_solver.rb', line 8

def error_vars
  @error_vars
end

#infeasible_rows ⇒ Object

Returns the value of attribute infeasible_rows.



8
9
10
 
# File 'lib/simplex_solver.rb', line 8

def infeasible_rows
  @infeasible_rows
end

#marker_vars ⇒ Object

Returns the value of attribute marker_vars.



8
9
10
 
# File 'lib/simplex_solver.rb', line 8

def marker_vars
  @marker_vars
end

#new_edit_constants ⇒ Object

Returns the value of attribute new_edit_constants.



8
9
10
 
# File 'lib/simplex_solver.rb', line 8

def new_edit_constants
  @new_edit_constants
end

#objective ⇒ Object

Returns the value of attribute objective.



8
9
10
 
# File 'lib/simplex_solver.rb', line 8

def objective
  @objective
end

#prev_edit_constants ⇒ Object

Returns the value of attribute prev_edit_constants.



8
9
10
 
# File 'lib/simplex_solver.rb', line 8

def prev_edit_constants
  @prev_edit_constants
end

#rows ⇒ Object

Returns the value of attribute rows.



8
9
10
 
# File 'lib/simplex_solver.rb', line 8

def rows
  @rows
end

#stay_minus_error_vars ⇒ Object

Returns the value of attribute stay_minus_error_vars.



8
9
10
 
# File 'lib/simplex_solver.rb', line 8

def stay_minus_error_vars
  @stay_minus_error_vars
end

#stay_plus_error_vars ⇒ Object

Returns the value of attribute stay_plus_error_vars.



8
9
10
 
# File 'lib/simplex_solver.rb', line 8

def stay_plus_error_vars
  @stay_plus_error_vars
end

Instance Method Details

#add_bounds(var, lower = nil, upper = nil) ⇒ Object 



16
17
18
19
 
# File 'lib/simplex_solver.rb', line 16

def add_bounds(var, lower = nil, upper = nil)
  add_constraint lower.cn_leq(var) if lower
  add_constraint var.cn_leq(upper) if upper
end

#add_constraint(constraint) ⇒ Object 



21
22
23
24
25
26
27
28
29
30
 
# File 'lib/simplex_solver.rb', line 21

def add_constraint(constraint)
  expr = make_expression(constraint)
  unless try_adding_directly(expr)
    add_with_artificial_variable(expr)
  end
  if auto_solve
    optimize(objective)
    set_external_variables
  end
end

#add_edit_var(variable, strength) ⇒ Object 



174
175
176
 
# File 'lib/simplex_solver.rb', line 174

def add_edit_var(variable, strength)
  add_constraint(EditConstraint.new variable: variable, strength: strength)
end

#add_stay(variable, strength = Strength::WeakStrength) ⇒ Object 



178
179
180
 
# File 'lib/simplex_solver.rb', line 178

def add_stay(variable, strength = Strength::WeakStrength)
  add_constraint(StayConstraint.new variable: variable, strength: strength)
end

#begin_edit ⇒ Object 



182
183
184
 
# File 'lib/simplex_solver.rb', line 182

def begin_edit
  self.new_edit_constants = [nil] * edit_vars.size
end

#end_edit ⇒ Object 



186
187
188
189
190
191
192
 
# File 'lib/simplex_solver.rb', line 186

def end_edit
  edit_constraints.each do |cn|
    remove_constraint(cn)
  end
  self.edit_vars = []
  self.edit_constraints = []
end

#note_added_variable(var, subject) ⇒ Object 



194
195
196
197
198
199
 
# File 'lib/simplex_solver.rb', line 194

def note_added_variable(var, subject)
  if subject
    columns[var] ||= Set.new
    columns[var] << subject
  end
end

#note_removed_variable(var, subject) ⇒ Object 



201
202
203
204
205
 
# File 'lib/simplex_solver.rb', line 201

def note_removed_variable(var, subject)
  if subject
    columns[var].delete(subject)
  end
end

#remove_constraint(cn) ⇒ Object 



32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
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
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
134
135
136
137
138
139
140
141
142
143
144
 
# File 'lib/simplex_solver.rb', line 32

def remove_constraint(cn)
  reset_stay_constants

  # remove any error variables from the objective function
  evars = error_vars.delete(cn) || []
  zrow = objective
  obj = rows[zrow]
  evars.each do |v|
    expr = rows[v]
    if expr.nil?
      obj.add_variable(v, cn.strength.symbolic_weight * -cn.weight, zrow, self)
    else
      obj.add_expression(expr, cn.strength.symbolic_weight * -cn.weight, zrow, self)
    end
  end

  exit_var = nil
  col = nil
  min_ratio = 0

  # try to make the marker variable basic, if it isn't already
  marker = marker_vars.delete(cn)
  unless rows.has_key? marker
    # choose which variable to move out of the basis. only consider restricted basic vars
    col = columns[marker]
    col.each do |v|
      if v.restricted?
        expr = rows[v]
        coeff = expr.coefficient_for(marker)
        # only consider negative coefficients
        if coeff < 0.0
          r = 0.0 - expr.constant / coeff
          if exit_var.nil? or r < min_ratio
            min_ratio = r
            exit_var = v
          end
        end
      end
    end

    # If exitVar is still nil at this point, then either the
    # marker variable has a positive coefficient in all equations,
    # or it only occurs in equations for unrestricted variables.
    # If it does occur in an equation for a restricted variable,
    # pick the equation that gives the smallest ratio.  (The row
    # with the marker variable will become infeasible, but all the
    # other rows will still be feasible; and we will be dropping
    # the row with the marker variable.  In effect we are removing
    # the non-negativity restriction on the marker variable.)
    if exit_var.nil?
      col.each do |v|
        if v.restricted?
          expr = rows[v]
          coeff = expr.coefficient_for(marker)
          r = expr.constant / coeff
          if exit_var.nil? or r < min_ratio
            min_ratio = r
            exit_var = v
          end
        end
      end
    end

    # If exitVar is still nil, and col is empty, then exitVar
    # doesn't occur in any equations, so just remove it.
    # Otherwise pick an exit var from among the unrestricted
    # variables whose equation involves the marker var
    if exit_var.nil?
      if col.empty?
        remove_parametric_var(marker)
      else
        exit_var = col.to_a.first
      end
    end

    if exit_var
      pivot(marker, exit_var)
    end
  end

  # Now delete any error variables.  If cn is an inequality, it
  # also contains a slack variable; but we use that as the
  # marker variable and so it has been deleted when we removed
  # its row
  if rows.has_key?(marker)
    remove_row(marker)
  end
  evars.each do |v|
    remove_parametric_var(v) unless v == marker
  end

  if cn.stay_constraint?
    self.stay_plus_error_vars = stay_plus_error_vars.reject do |v| evars.include? v end
    self.stay_minus_error_vars = stay_minus_error_vars.reject do |v| evars.include? v end
  end

  if cn.edit_constraint?
    # find the index in editPlusErrorVars of the error variable for this constraint
    index = find_edit_error_index(evars)

    # remove the error variables from editPlusErrorVars and editMinusErrorVars
    edit_plus_error_vars.delete_at(index)
    edit_minus_error_vars.delete_at(index)

    # remove the constants from prevEditConstants
    prev_edit_constants.delete_at(index)
  end

  if auto_solve
    optimize(zrow)
    set_external_variables
  end
end

#resolve(cs = nil) ⇒ Object 



146
147
148
149
150
151
152
153
154
155
156
157
 
# File 'lib/simplex_solver.rb', line 146

def resolve(cs = nil)
  if cs
    self.new_edit_constants = cs
  end

  # Re-solve the current collection of constraints for the new values in newEditConstants.
  self.infeasible_rows = []
  reset_stay_constants
  reset_edit_constants
  dual_optimize
  set_external_variables
end

#solve ⇒ Object 



159
160
161
162
 
# File 'lib/simplex_solver.rb', line 159

def solve
  optimize objective
  set_external_variables
end

#suggest_value(var, val) ⇒ Object

Raises:



164
165
166
167
168
169
170
171
172
 
# File 'lib/simplex_solver.rb', line 164

def suggest_value(var, val)
  edit_vars.each_with_index do |v, idx|
    if v == var
      new_edit_constants[idx] = val
      return self
    end
  end
  raise InternalError, "variable not currently being edited"
end