Module: Quicopt::Wire

Defined in:
lib/quicopt/wire.rb

Overview

Node constructors over the generated protobuf classes, and the translation from the DSL's collected polynomials into the message's expression trees.

Constant Summary collapse

PB =

The generated protobuf classes — Program, Expression, Constraint, … Aliased for brevity throughout this file.

Quicopt::Modeler::V1

Class Method Summary collapse

Class Method Details

.apply(op, args) ⇒ Object

An operator application: op applied to child expressions.



115
116
117
 
# File 'lib/quicopt/wire.rb', line 115

def apply(op, args)
  PB::Expression.new(apply: PB::Apply.new(op: op, args: args))
end

.block_decl(block) ⇒ PB::BlockDecl

A block → BlockDecl: its name and its variables, in the order given.

Parameters:

Returns:

  • (PB::BlockDecl) 


259
260
261
262
 
# File 'lib/quicopt/wire.rb', line 259

def block_decl(block)
  PB::BlockDecl.new(name: block.name,
                    members: block.variables.map { |v| PB::VarRef.new(name: v.name, index: PB::Index.new) })
end

.condition(cond) ⇒ PB::Expression

A 0/1 term: indicator(e), step(e), or step(tol − abs(e)) for a comparison with a tolerance.

Parameters:

Returns:

  • (PB::Expression) 


198
199
200
201
202
203
204
205
206
 
# File 'lib/quicopt/wire.rb', line 198

def condition(cond)
  arg = expression(cond.argument)
  case cond.op
  when :indicator then apply("indicator", [arg])
  when :step then apply("step", [arg])
  when :near then apply("step", [apply("-", [const(cond.tol), apply("abs", [arg])])])
  else raise Error, "unknown condition #{cond.op.inspect}"
  end
end

.const(value) ⇒ Object

A constant expression node. The oneof case is always set, so a constant 0.0 survives the round-trip rather than vanishing as a protobuf default.



91
92
93
 
# File 'lib/quicopt/wire.rb', line 91

def const(value)
  PB::Expression.new(constant: number(value))
end

.constraint(con) ⇒ PB::Constraint

One DSL constraint row → one constraint in the message.

Parameters:

Returns:

  • (PB::Constraint) 


268
269
270
271
272
273
274
275
276
277
 
# File 'lib/quicopt/wire.rb', line 268

def constraint(con)
  f = expression(con.body)
  c = con.bound
  case con.sense
  when :eq then PB::Constraint.new(f: minus(f, c), set: con_set(:zero))
  when :ge then PB::Constraint.new(f: minus(f, c), set: con_set(:nonneg))
  when :le then PB::Constraint.new(f: geq(c, f), set: con_set(:nonneg))
  else raise Error, "unknown constraint sense #{con.sense.inspect}"
  end
end

.decode(bytes) ⇒ PB::Program

Parse bytes back into a Program — the inverse of encode, and the only sound way to compare two encodings.

Parameters:

  • bytes (String)

Returns:

  • (PB::Program) 


83
84
85
 
# File 'lib/quicopt/wire.rb', line 83

def decode(bytes)
  PB::Program.decode(bytes)
end

.encode(model) ⇒ String

Encode a model (or an already-built Program) to bytes.

Parameters:

Returns:

  • (String) —

    binary protobuf bytes



74
75
76
 
# File 'lib/quicopt/wire.rb', line 74

def encode(model)
  PB::Program.encode(model.is_a?(PB::Program) ? model : program(model))
end

.expression(expr) ⇒ PB::Expression

A collected DSL expression → the message's expression tree: the constant (when nonzero), then the linear terms, then the quadratic ones — the term order the Python and Julia clients use.

Parameters:

Returns:

  • (PB::Expression) 


153
154
155
156
157
158
159
 
# File 'lib/quicopt/wire.rb', line 153

def expression(expr)
  terms = []
  terms << const(expr.constant) unless expr.constant.zero?
  expr.linear.each { |v, c| terms << scaled(c, factor(v)) }
  expr.quadratic.each { |(a, b), c| terms << scaled(c, apply("*", [factor(a), factor(b)])) }
  sum(terms)
end

.factor(factor) ⇒ PB::Expression

One factor of a term: a variable, a read of a permutation, partition or lookup table (each standing for its value counted from 0), or a term that switches.

Parameters:

Returns:

  • (PB::Expression) 


168
169
170
171
172
173
174
175
176
177
178
179
180
181
 
# File 'lib/quicopt/wire.rb', line 168

def factor(factor)
  case factor
  when Variable then var(factor.name)
  when Placement
    apply("-", [apply(factor.op.to_s, [const(factor.position + 1), structure(factor.permutation.name)]),
                const(1.0)])
  when PartRead then part_read(factor)
  when TableEntry then table(factor.table.name, factor.index.map { |e| one_based(e) })
  when Condition then condition(factor)
  when Extremum
    factor.args.map { |a| expression(a) }.reduce { |acc, e| apply(factor.op.to_s, [acc, e]) }
  else raise Error, "unknown factor #{factor.inspect}"
  end
end

.number(value) ⇒ Object

Flatten negative zero before encoding.

IEEE keeps -0.0 distinct from 0.0 — a distinct bit pattern, and a distinct protobuf value — and moving a bound across an inequality (f ≤ 0 ⇒ 0 − f ≥ 0) produces one whenever that bound is zero. The Python and Julia clients send 0.0 there, so collapse the sign here rather than sending bytes that differ from theirs by a sign bit.



103
104
105
106
 
# File 'lib/quicopt/wire.rb', line 103

def number(value)
  float = value.to_f
  float.zero? ? 0.0 : float
end

.one_based(position) ⇒ PB::Expression

A table position, counted from 0 in the DSL, as the wire's position counted from 1: a whole number moves up by one, a read of a permutation loses the − 1 its own shift added, and anything else gains + 1.

Parameters:

Returns:

  • (PB::Expression) 


214
215
216
217
218
219
220
221
 
# File 'lib/quicopt/wire.rb', line 214

def one_based(position)
  return const(position.constant + 1) if position.constant?

  e = expression(position)
  down = e.node == :apply && e.apply.op == "-" && e.apply.args.size == 2 &&
         e.apply.args[1].node == :constant && e.apply.args[1].constant == 1.0
  down ? e.apply.args[0] : apply("+", [e, const(1.0)])
end

.param_table(table) ⇒ PB::ParamTable

A lookup table → ParamTable: one entry per cell, keyed by its positions counted from 1, in row-major order.

Parameters:

Returns:

  • (PB::ParamTable) 


228
229
230
231
232
233
234
235
 
# File 'lib/quicopt/wire.rb', line 228

def param_table(table)
  cells = table.shape.map { |extent| (0...extent).to_a }
  keys = cells.first.product(*cells.drop(1))
  PB::ParamTable.new(name: table.name, entries: keys.map do |key|
    PB::ParamEntry.new(key: PB::Index.new(elems: key.map { |k| PB::IndexElem.new(int: k + 1) }),
                       value: number(key.reduce(table.values) { |row, k| row[k] }))
  end)
end

.part_read(read) ⇒ PB::Expression

A read of a partition: the part, shifted to count from 0; the size, a count, as it is.

Parameters:

Returns:

  • (PB::Expression) 


188
189
190
191
 
# File 'lib/quicopt/wire.rb', line 188

def part_read(read)
  node = apply(read.op.to_s, [const(read.position + 1), structure(read.partition.name)])
  read.op == :part_of ? apply("-", [node, const(1.0)]) : node
end

.program(model) ⇒ PB::Program

Turn model into the Program message the service reads.

Parameters:

Returns:

  • (PB::Program) 


58
59
60
61
62
63
64
65
66
67
68
 
# File 'lib/quicopt/wire.rb', line 58

def program(model)
  PB::Program.new(
    params: model.tables.sort_by(&:name).map { |t| param_table(t) },
    vars: model.variables.map { |v| var_decl(v) },
    objective: expression(model.objective),
    sense: model.sense,
    constraints: model.constraints.map { |c| constraint(c) },
    structures: (model.permutations + model.partitions).sort_by(&:name).map { |p| structure_decl(p) },
    blocks: model.blocks.sort_by(&:name).map { |b| block_decl(b) }
  )
end

.scaled(coef, expr) ⇒ Object

coef · expr, dropping a unit coefficient.



131
132
133
 
# File 'lib/quicopt/wire.rb', line 131

def scaled(coef, expr)
  coef == 1.0 ? expr : apply("*", [const(coef), expr])
end

.structure(name) ⇒ Object

A reference to a declared permutation, by name.



120
121
122
 
# File 'lib/quicopt/wire.rb', line 120

def structure(name)
  PB::Expression.new(structure: PB::StructRef.new(name: name))
end

.structure_decl(structure) ⇒ PB::StructureDecl

A permutation or a partition → StructureDecl, its start (and a permutation's precedences) counted from 1.

Parameters:

Returns:

  • (PB::StructureDecl) 


242
243
244
245
246
247
248
249
250
251
252
253
 
# File 'lib/quicopt/wire.rb', line 242

def structure_decl(structure)
  start = (structure.start || []).map { |k| k + 1 }
  if structure.is_a?(Partition)
    return PB::StructureDecl.new(name: structure.name, kind: "partition", size: structure.n_items,
                                 start: start, fixed: false, parts: structure.n_parts)
  end

  PB::StructureDecl.new(
    name: structure.name, kind: "permutation", size: structure.n_items, start: start, fixed: false,
    precede: structure.precedences.map { |a, b| PB::Precedence.new(before: a + 1, after: b + 1) }
  )
end

.sum(terms) ⇒ Object

Fold terms into an n-ary sum, dropping additive-zero constants. No terms is the zero constant; one term is itself.



137
138
139
140
141
142
143
 
# File 'lib/quicopt/wire.rb', line 137

def sum(terms)
  surviving = terms.reject { |t| t.node == :constant && t.constant.zero? }
  return const(0.0) if surviving.empty?
  return surviving.first if surviving.size == 1

  apply("+", surviving)
end

.table(param, index) ⇒ Object

A read of the parameter table param at the given positions (counted from 1, as on the wire).



126
127
128
 
# File 'lib/quicopt/wire.rb', line 126

def table(param, index)
  PB::Expression.new(table: PB::TableRef.new(param: param, index: index))
end

.var(name) ⇒ Object

A reference to a flat (unindexed) variable. The Index message is sent present-but-empty, which is what the service expects.



110
111
112
 
# File 'lib/quicopt/wire.rb', line 110

def var(name)
  PB::Expression.new(var: PB::VarRef.new(name: name, index: PB::Index.new))
end

.var_decl(variable) ⇒ PB::VarDecl

A variable declaration → VarDecl. Bounds are plain numbers (the message can also take a bound from a parameter table, but that needs indexed variables, which this DSL does not have); ±Inf passes straight through and means "unbounded in that direction". A variable that may also be 0 goes out with its domain, SEMICONTINUOUS or SEMIINTEGER.

Parameters:

Returns:

  • (PB::VarDecl) 


287
288
289
290
291
292
293
 
# File 'lib/quicopt/wire.rb', line 287

def var_decl(variable)
  PB::VarDecl.new(name: variable.name,
                  domain: variable.domain,
                  lower: PB::Bound.new(scalar: number(variable.lower)),
                  upper: PB::Bound.new(scalar: number(variable.upper)),
                  start: number(variable.start))
end