Class: Quicopt::Expression

Inherits:
Object
  • Object
show all
Includes:
Operators
Defined in:
lib/quicopt/model.rb

Overview

A polynomial of degree ≤ 2 over a model's variables, always kept in collected form: +constant + Σ cᵢ·xᵢ + Σ qᵢⱼ·xᵢxⱼ+.

Instances are immutable — every operator returns a new expression — so an expression can be shared, reused and stored without aliasing surprises.

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Operators

#!=, #*, #**, #+, #+@, #-, #-@, #/, #<=, #==, #>=, #coerce

Constructor Details

#initialize(constant: 0.0, linear: {}, quadratic: {}) ⇒ Expression

Returns a new instance of Expression.



243
244
245
246
247
248
 
# File 'lib/quicopt/model.rb', line 243

def initialize(constant: 0.0, linear: {}, quadratic: {})
  @constant = constant.to_f
  @linear = linear.freeze
  @quadratic = quadratic.freeze
  freeze
end

Instance Attribute Details

#constant ⇒ Float (readonly)

Returns the constant term.

Returns:

  • (Float) —

    the constant term



236
237
238
 
# File 'lib/quicopt/model.rb', line 236

def constant
  @constant
end

#linear ⇒ Hash{Variable=>Float} (readonly)

Returns linear coefficients, in insertion order.

Returns:

  • (Hash{Variable=>Float}) —

    linear coefficients, in insertion order



238
239
240
 
# File 'lib/quicopt/model.rb', line 238

def linear
  @linear
end

#quadratic ⇒ Hash{Array(Variable,Variable)=>Float} (readonly)

Returns quadratic coefficients, keyed by the factor pair in model order, in insertion order.

Returns:

  • (Hash{Array(Variable,Variable)=>Float}) —

    quadratic coefficients, keyed by the factor pair in model order, in insertion order



241
242
243
 
# File 'lib/quicopt/model.rb', line 241

def quadratic
  @quadratic
end

Class Method Details

.cast(value) ⇒ Object

Coerce a number, variable or expression into an Expression.

Raises:

  • (TypeError) —

    for anything else



258
259
260
261
262
263
264
265
266
 
# File 'lib/quicopt/model.rb', line 258

def self.cast(value)
  case value
  when Expression then value
  when Variable then value.to_expr
  when Numeric then new(constant: value)
  else
    raise TypeError, "cannot use #{value.class} in a Quicopt expression"
  end
end

.castable?(value) ⇒ Boolean

Returns whether value can become an expression.

Returns:

  • (Boolean) —

    whether value can become an expression



251
252
253
 
# File 'lib/quicopt/model.rb', line 251

def self.castable?(value)
  value.is_a?(Expression) || value.is_a?(Variable) || value.is_a?(Numeric)
end

.merge(left, right) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Sum two coefficient maps, dropping terms that cancel exactly.



368
369
370
371
372
373
374
375
 
# File 'lib/quicopt/model.rb', line 368

def self.merge(left, right)
  return left.dup if right.empty?
  return right.dup if left.empty?

  out = left.dup
  right.each { |k, c| out[k] = (out[k] || 0.0) + c }
  prune(out)
end

.pair(left, right) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

The canonical key for a quadratic term: the two factors in model order, so x*y and y*x accumulate on one coefficient.



389
390
391
 
# File 'lib/quicopt/model.rb', line 389

def self.pair(left, right)
  (left.index <= right.index ? [left, right] : [right, left]).freeze
end

.prune(terms) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Drop exactly-zero coefficients, so a cancelled term leaves no trace on the wire.



381
382
383
 
# File 'lib/quicopt/model.rb', line 381

def self.prune(terms)
  terms.reject { |_, c| c.zero? }
end

Instance Method Details

#constant? ⇒ Boolean

Returns whether this is a bare constant.

Returns:

  • (Boolean) —

    whether this is a bare constant



282
283
284
 
# File 'lib/quicopt/model.rb', line 282

def constant?
  degree.zero?
end

#degree ⇒ Integer

Returns 0, 1 or 2 — the highest degree present.

Returns:

  • (Integer) —

    0, 1 or 2 — the highest degree present



274
275
276
277
278
279
 
# File 'lib/quicopt/model.rb', line 274

def degree
  return 2 unless @quadratic.empty?
  return 1 unless @linear.empty?

  0
end

#eq?(other) ⇒ Boolean

Returns value equality — the same constant and the same coefficient maps. Named eq? because == builds a constraint row.

Returns:

  • (Boolean) —

    value equality — the same constant and the same coefficient maps. Named eq? because == builds a constraint row.



360
361
362
363
 
# File 'lib/quicopt/model.rb', line 360

def eq?(other)
  other.is_a?(Expression) && @constant == other.constant &&
    @linear == other.linear && @quadratic == other.quadratic
end

#inspect ⇒ String

Returns the polynomial, tagged with the class.

Returns:

  • (String) —

    the polynomial, tagged with the class



354
355
356
 
# File 'lib/quicopt/model.rb', line 354

def inspect
  "#<Quicopt::Expression #{self}>"
end

#plus(other) ⇒ Expression

Returns +self + other+.

Returns:



287
288
289
290
291
 
# File 'lib/quicopt/model.rb', line 287

def plus(other)
  Expression.new(constant: @constant + other.constant,
                 linear: Expression.merge(@linear, other.linear),
                 quadratic: Expression.merge(@quadratic, other.quadratic))
end

#scale(factor) ⇒ Expression

Returns self scaled by the numeric factor.

Returns:

  • (Expression) —

    self scaled by the numeric factor



294
295
296
297
298
299
300
301
 
# File 'lib/quicopt/model.rb', line 294

def scale(factor)
  f = factor.to_f
  return Expression.new if f.zero?

  Expression.new(constant: @constant * f,
                 linear: @linear.transform_values { |c| c * f },
                 quadratic: @quadratic.transform_values { |c| c * f })
end

#times(other) ⇒ Expression

Multiply two expressions, staying at degree 2 or below.

A constant factor just scales; two linear factors expand into quadratic terms. Anything else would exceed degree 2 and raises instead.

Returns:

Raises:



310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
 
# File 'lib/quicopt/model.rb', line 310

def times(other)
  return scale(other.constant) if other.constant?
  return other.scale(@constant) if constant?

  if degree > 1 || other.degree > 1
    raise UnsupportedExpression,
          "multiplying degree #{degree} by degree #{other.degree} gives a cubic or " \
          "higher term; a Quicopt model is linear or quadratic"
  end

  quadratic = {}
  @linear.each do |va, ca|
    other.linear.each do |vb, cb|
      key = Expression.pair(va, vb)
      quadratic[key] = (quadratic[key] || 0.0) + (ca * cb)
    end
  end
  Expression.new(constant: @constant * other.constant,
                 linear: Expression.merge(@linear.transform_values { |c| c * other.constant },
                                          other.linear.transform_values { |c| c * @constant }),
                 quadratic: Expression.prune(quadratic))
end

#to_expr ⇒ Expression

Returns self.

Returns:



269
270
271
 
# File 'lib/quicopt/model.rb', line 269

def to_expr
  self
end

#to_s ⇒ Object

Renders the polynomial, e.g. +3x + 2y - 4+.



343
344
345
346
347
348
349
350
351
 
# File 'lib/quicopt/model.rb', line 343

def to_s
  terms = []
  terms << Format.number(@constant) unless @constant.zero?
  @linear.each { |v, c| terms << Format.term(c, v.name) }
  @quadratic.each { |(a, b), c| terms << Format.term(c, "#{a.name}*#{b.name}") }
  return "0" if terms.empty?

  terms.join(" + ").gsub(" + -", " - ")
end

#variables ⇒ Array<Variable>

Every variable this expression mentions, in first-use order.

Returns:



336
337
338
339
340
 
# File 'lib/quicopt/model.rb', line 336

def variables
  seen = @linear.keys
  @quadratic.each_key { |a, b| seen |= [a, b] }
  seen
end