Class: Opt::Problem

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Problem

Returns a new instance of Problem.



5
6
7
8
 
# File 'lib/opt/problem.rb', line 5

def initialize
  @constraints = []
  @indexed_constraints = []
end

Instance Attribute Details

#constraints ⇒ Object (readonly)

Returns the value of attribute constraints.



3
4
5
 
# File 'lib/opt/problem.rb', line 3

def constraints
  @constraints
end

#objective ⇒ Object (readonly)

Returns the value of attribute objective.



3
4
5
 
# File 'lib/opt/problem.rb', line 3

def objective
  @objective
end

#sense ⇒ Object (readonly)

Returns the value of attribute sense.



3
4
5
 
# File 'lib/opt/problem.rb', line 3

def sense
  @sense
end

Instance Method Details

#add(constraint) ⇒ Object

Raises:

  • (ArgumentError) 


10
11
12
13
14
15
 
# File 'lib/opt/problem.rb', line 10

def add(constraint)
  raise ArgumentError, "Expected Comparison" unless constraint.is_a?(Comparison)

  @constraints << constraint
  @indexed_constraints << index_constraint(constraint)
end

#inspect ⇒ Object 



140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
 
# File 'lib/opt/problem.rb', line 140

def inspect
  str = String.new("")
  str << "#{@sense}\n  #{@objective.inspect}\n"
  str << "subject to\n"
  @constraints.each do |constraint|
    str << "  #{constraint.inspect}\n"
  end
  str << "vars\n"
  vars.each do |var|
    bounds = var.bounds
    end_op = bounds.exclude_end? ? "<" : "<="
    var_str =
      if bounds.begin && bounds.end
        "#{bounds.begin} <= #{var.name} #{end_op} #{bounds.end}"
      elsif var.bounds.begin
        "#{var.name} >= #{bounds.begin}"
      else
        "#{var.name} #{end_op} #{bounds.end}"
      end
    if var.is_a?(SemiContinuous) || var.is_a?(SemiInteger)
      var_str = "#{var_str} or #{var.name} = 0"
    end
    str << "  #{var_str}\n"
  end
  str
end

#maximize(objective) ⇒ Object 



21
22
23
 
# File 'lib/opt/problem.rb', line 21

def maximize(objective)
  set_objective(:maximize, objective)
end

#minimize(objective) ⇒ Object 



17
18
19
 
# File 'lib/opt/problem.rb', line 17

def minimize(objective)
  set_objective(:minimize, objective)
end

#solve(solver: nil, verbose: false, time_limit: nil) ⇒ Object

Raises:



25
26
27
28
29
30
31
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
 
# File 'lib/opt/problem.rb', line 25

def solve(solver: nil, verbose: false, time_limit: nil)
  @indexed_objective ||= {}

  vars = self.vars
  raise Error, "No variables" if vars.empty?
  has_semi_continuous_var = vars.any? { |v| v.is_a?(SemiContinuous) }
  has_semi_integer_var = vars.any? { |v| v.is_a?(SemiInteger) }
  has_integer_var = vars.any? { |v| v.is_a?(Integer) }
  type = has_semi_continuous_var || has_semi_integer_var || has_integer_var ? :mip : :lp
  quadratic = @indexed_objective.any? { |k, _| k.is_a?(Array) }

  if quadratic
    raise Error, "Not supported" if type == :mip
    type = :qp
  end

  raise Error, "No solvers found" if Opt.available_solvers.empty?

  solver ||= (Opt.default_solvers[type] || Opt.available_solvers.find { |s| Opt.solvers[s].supports_type?(type) })
  raise Error, "No solvers found for #{type}" unless solver

  # TODO better error message
  solver_cls = Opt.solvers.fetch(solver)
  raise Error, "Solver does not support #{type}" unless solver_cls.supports_type?(type)

  raise Error, "Solver does not support semi-continuous variables" if has_semi_continuous_var && !solver_cls.supports_semi_continuous_variables?
  raise Error, "Solver does not support semi-integer variables" if has_semi_integer_var && !solver_cls.supports_semi_integer_variables?

  col_lower = []
  col_upper = []
  obj = []

  @sense ||= :minimize

  vars.each do |var|
    col_lower << (var.bounds.begin || -Float::INFINITY)
    upper = var.bounds.end
    if upper && var.bounds.exclude_end?
      case var
      when Integer, SemiInteger
        upper -= 1
      else
        upper -= Float::EPSILON
      end
    end
    col_upper << (upper || Float::INFINITY)
    obj << (@indexed_objective[var] || 0)
  end

  row_lower = []
  row_upper = []
  constraints_by_var = @indexed_constraints
  constraints_by_var.each do |left, op, right|
    case op
    when :>=
      row_lower << right
      row_upper << Float::INFINITY
    when :<=
      row_lower << -Float::INFINITY
      row_upper << right
    else # :==
      row_lower << right
      row_upper << right
    end
  end

  start = []
  index = []
  value = []

  vars.each do |var|
    start << index.size
    constraints_by_var.map(&:first).each_with_index do |ic, i|
      if ic[var]
        index << i
        value << ic[var]
      end
    end
  end
  start << index.size

  if type == :qp
    @indexed_objective.select { |k, _| k.is_a?(Array) }.each do |k, v|
      @indexed_objective[k.reverse] = v
    end
  end

  res = solver_cls.new.solve(
    sense: @sense, start: start, index: index, value: value,
    col_lower: col_lower, col_upper: col_upper, obj: obj,
    row_lower: row_lower, row_upper: row_upper,
    constraints_by_var: constraints_by_var, vars: vars,
    offset: @indexed_objective[nil] || 0, verbose: verbose,
    type: type, time_limit: time_limit, indexed_objective: @indexed_objective
  )

  if res[:status] == :optimal
    vars.zip(res.delete(:x)) do |a, b|
      a.value =
        case a
        when Binary
          b.round != 0
        when Integer, SemiInteger
          b.round
        else
          b
        end
    end
  else
    res.delete(:objective)
    res.delete(:x)
  end
  res
end