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ⱼ.

A value read from a permutation (route.item_at(0)) or a lookup table (dist[i, j]) counts as one factor, like a variable: 2 * dist[i, j] is linear, x * dist[i, j] quadratic.

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.



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

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



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

def constant
  @constant
end

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

Returns linear coefficients, in insertion order. A read of a permutation or lookup table is a key here too.

Returns:

  • (Hash{Variable=>Float}) —

    linear coefficients, in insertion order. A read of a permutation or lookup table is a key here too.



292
293
294
 
# File 'lib/quicopt/model.rb', line 292

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



295
296
297
 
# File 'lib/quicopt/model.rb', line 295

def quadratic
  @quadratic
end

Class Method Details

.cast(value) ⇒ Object

Coerce a number, variable or expression into an Expression.

Raises:

  • (TypeError) —

    for anything else



312
313
314
315
316
317
318
319
320
 
# File 'lib/quicopt/model.rb', line 312

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



305
306
307
 
# File 'lib/quicopt/model.rb', line 305

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.



432
433
434
435
436
437
438
439
 
# File 'lib/quicopt/model.rb', line 432

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.



453
454
455
 
# File 'lib/quicopt/model.rb', line 453

def self.pair(left, right)
  ((left.order <=> right.order) <= 0 ? [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.



445
446
447
 
# File 'lib/quicopt/model.rb', line 445

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



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

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



328
329
330
331
332
333
 
# File 'lib/quicopt/model.rb', line 328

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.



424
425
426
427
 
# File 'lib/quicopt/model.rb', line 424

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

#factors ⇒ Array<Variable, Placement, TableEntry, Condition, Extremum>

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.

Every factor of every term — variables and reads of permutations and lookup tables — in first-use order.

Returns:



400
401
402
403
404
 
# File 'lib/quicopt/model.rb', line 400

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

#inspect ⇒ String

Returns the polynomial, tagged with the class.

Returns:

  • (String) —

    the polynomial, tagged with the class



418
419
420
 
# File 'lib/quicopt/model.rb', line 418

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

#plus(other) ⇒ Expression

Returns self + other.

Returns:



341
342
343
344
345
 
# File 'lib/quicopt/model.rb', line 341

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



348
349
350
351
352
353
354
355
 
# File 'lib/quicopt/model.rb', line 348

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:



364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
 
# File 'lib/quicopt/model.rb', line 364

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:



323
324
325
 
# File 'lib/quicopt/model.rb', line 323

def to_expr
  self
end

#to_s ⇒ Object

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



407
408
409
410
411
412
413
414
415
 
# File 'lib/quicopt/model.rb', line 407

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

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

#variables ⇒ Array<Variable>

Every variable this expression mentions, in first-use order — including those in the positions of a lookup table read.

Returns:



391
392
393
 
# File 'lib/quicopt/model.rb', line 391

def variables
  factors.flat_map(&:variables).uniq
end