Class: Quicopt::Expression

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

Overview

A normalised polynomial of degree ≤ 2 over a model's variables: +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.



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

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



233
234
235
 
# File 'lib/quicopt/model.rb', line 233

def constant
  @constant
end

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

Returns linear coefficients, in insertion order.

Returns:

  • (Hash{Variable=>Float}) —

    linear coefficients, in insertion order



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

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



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

def quadratic
  @quadratic
end

Class Method Details

.cast(value) ⇒ Object

Coerce a number, variable or expression into an Expression.

Raises:

  • (TypeError) —

    for anything else



255
256
257
258
259
260
261
262
263
 
# File 'lib/quicopt/model.rb', line 255

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



248
249
250
 
# File 'lib/quicopt/model.rb', line 248

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.



364
365
366
367
368
369
370
371
 
# File 'lib/quicopt/model.rb', line 364

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.



385
386
387
 
# File 'lib/quicopt/model.rb', line 385

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.



377
378
379
 
# File 'lib/quicopt/model.rb', line 377

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



279
280
281
 
# File 'lib/quicopt/model.rb', line 279

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



271
272
273
274
275
276
 
# File 'lib/quicopt/model.rb', line 271

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.



356
357
358
359
 
# File 'lib/quicopt/model.rb', line 356

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



350
351
352
 
# File 'lib/quicopt/model.rb', line 350

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

#plus(other) ⇒ Expression

Returns +self + other+.

Returns:



284
285
286
287
288
 
# File 'lib/quicopt/model.rb', line 284

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



291
292
293
294
295
296
297
298
 
# File 'lib/quicopt/model.rb', line 291

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 inside the degree-2 subset.

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

Returns:

Raises:



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

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

  if degree > 1 || other.degree > 1
    raise UnsupportedExpression,
          "product of degree #{degree} and degree #{other.degree} exceeds the quadratic subset"
  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:



266
267
268
 
# File 'lib/quicopt/model.rb', line 266

def to_expr
  self
end

#to_s ⇒ Object

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



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

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:



332
333
334
335
336
 
# File 'lib/quicopt/model.rb', line 332

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