Class: Quicopt::Model

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

Overview

An optimization model: variables, one objective, and constraint rows.

m = Quicopt::Model.new
x = m.int_var(0, 4, "x")
y = m.bin_var("y")
m.maximize(3 * x + 2 * y)
m.add(x + y <= 5)

You build the model; to_program / encode turn it into the message the service reads, and Quicopt::Client#solve sends it.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Model

Returns a new instance of Model.



545
546
547
548
549
550
551
552
553
554
555
556
557
558
 
# File 'lib/quicopt/model.rb', line 545

def initialize
  @variables = []
  @by_name = {}
  @permutations = []
  @partitions = []
  @tables = []
  @blocks = []
  @structured = {}
  @interned = {}
  @reads = 0
  @constraints = []
  @objective = Expression.new
  @sense = "min"
end

Instance Attribute Details

#blocks ⇒ Array<Block> (readonly)

Returns the declared blocks, in declaration order.

Returns:

  • (Array<Block>) —

    the declared blocks, in declaration order



543
544
545
 
# File 'lib/quicopt/model.rb', line 543

def blocks
  @blocks
end

#constraints ⇒ Array<Constraint> (readonly)

Returns the constraint rows, in insertion order.

Returns:

  • (Array<Constraint>) —

    the constraint rows, in insertion order



531
532
533
 
# File 'lib/quicopt/model.rb', line 531

def constraints
  @constraints
end

#objective ⇒ Expression (readonly)

Returns the objective (the zero expression until set).

Returns:

  • (Expression) —

    the objective (the zero expression until set)



533
534
535
 
# File 'lib/quicopt/model.rb', line 533

def objective
  @objective
end

#partitions ⇒ Array<Partition> (readonly)

Returns the declared partitions, in declaration order.

Returns:

  • (Array<Partition>) —

    the declared partitions, in declaration order



541
542
543
 
# File 'lib/quicopt/model.rb', line 541

def partitions
  @partitions
end

#permutations ⇒ Array<Permutation> (readonly)

Returns the declared permutations, in declaration order.

Returns:

  • (Array<Permutation>) —

    the declared permutations, in declaration order



537
538
539
 
# File 'lib/quicopt/model.rb', line 537

def permutations
  @permutations
end

#sense ⇒ String (readonly)

Returns "min" or "max".

Returns:

  • (String) —

    "min" or "max"



535
536
537
 
# File 'lib/quicopt/model.rb', line 535

def sense
  @sense
end

#tables ⇒ Array<LookupTable> (readonly)

Returns the declared lookup tables, in declaration order.

Returns:

  • (Array<LookupTable>) —

    the declared lookup tables, in declaration order



539
540
541
 
# File 'lib/quicopt/model.rb', line 539

def tables
  @tables
end

#variables ⇒ Array<Variable> (readonly)

Returns the declared variables, in declaration order.

Returns:

  • (Array<Variable>) —

    the declared variables, in declaration order



529
530
531
 
# File 'lib/quicopt/model.rb', line 529

def variables
  @variables
end

Instance Method Details

#add(constraint) ⇒ Constraint

Add a constraint row built by <=, >= or ==.

Parameters:

Returns:

Raises:

  • (TypeError) —

    if handed something that is not a constraint — most often a bare expression, or a comparison Ruby already reduced to a boolean

  • (ArgumentError) —

    for a comparison with <, > or !=, which no row can express



837
838
839
840
841
842
843
844
845
846
847
848
849
850
 
# File 'lib/quicopt/model.rb', line 837

def add(constraint)
  unless constraint.is_a?(Constraint)
    raise TypeError,
          "add expects a constraint such as `x + y <= 5`, got #{constraint.class}"
  end
  unless Constraint::ROWS.include?(constraint.sense)
    raise ArgumentError,
          "#{constraint} is not a constraint Quicopt can hold: use <=, >= or ==, " \
          "or turn the comparison into a 0/1 expression with Quicopt.holds"
  end
  check_ownership(constraint.expr)
  @constraints << constraint
  constraint
end

#bin_var(name = nil, start: nil) ⇒ Variable

Declare a binary variable.

Returns:



608
609
610
 
# File 'lib/quicopt/model.rb', line 608

def bin_var(name = nil, start: nil)
  declare(:BINARY, 0.0, 1.0, name, start)
end

#block(name, vars) ⇒ Block

Declare the variables of one subproblem as a block: one customer's supply, one project's staffing. The constraints over a block's own variables alone, such as that customer's demand, hold in every solution the service returns. A block changes nothing else about the model: the same solutions are feasible and the objective is the same.

supply = (0...3).map { |w| m.int_var(10, 25, "ship_#{w}", semi: true) }
m.block("customer", supply)

Parameters:

  • name (String, Symbol) —

    the block's name, distinct from every other block's

  • vars (Array<Variable>) —

    its variables, each with finite bounds and in no other block

Returns:

Raises:

  • (TypeError) —

    if a member is not a variable

  • (ArgumentError) —

    if the block is empty, the name is taken, a member belongs to another model or block or has an infinite bound



737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
 
# File 'lib/quicopt/model.rb', line 737

def block(name, vars)
  raise TypeError, "a block's name is a String or a Symbol, got #{name.inspect}" unless name.is_a?(String) || name.is_a?(Symbol)

  nm = name.to_s
  raise ArgumentError, "a block's name cannot be empty" if nm.empty?
  raise ArgumentError, "there is already a block named #{nm.inspect}" if @blocks.any? { |b| b.name == nm }

  members = Array(vars)
  raise ArgumentError, "block #{nm.inspect} has no variables" if members.empty?

  members.each_with_index do |v, k|
    raise TypeError, "block #{nm.inspect}: a member is a variable, got #{v.class}" unless v.is_a?(Variable)
    raise ArgumentError, "variable #{v.name.inspect} belongs to a different Quicopt::Model" unless v.model.equal?(self)
    raise ArgumentError, "variable #{v.name.inspect} is listed twice in block #{nm.inspect}" if members[0...k].any? { |u| u.equal?(v) }
    if (owner = @blocks.find { |b| b.variables.any? { |u| u.equal?(v) } })
      raise ArgumentError, "variable #{v.name.inspect} is already in block #{owner.name.inspect}"
    end
    unless v.lower.finite? && v.upper.finite?
      raise ArgumentError, "variable #{v.name.inspect} has bounds [#{v.lower}, #{v.upper}]; " \
                           "a block's variables need finite bounds"
    end
  end
  block = Block.new(nm, members.dup.freeze)
  @blocks << block
  block
end

#encode ⇒ String

Turn this model into the message the service reads and encode it.

Returns:

  • (String) —

    binary protobuf bytes



862
863
864
 
# File 'lib/quicopt/model.rb', line 862

def encode
  Wire.encode(self)
end

#inspect ⇒ String

Returns a one-line summary: variable and row counts.

Returns:

  • (String) —

    a one-line summary: variable and row counts



888
889
890
 
# File 'lib/quicopt/model.rb', line 888

def inspect
  "#<Quicopt::Model #{@variables.size} vars, #{@constraints.size} constraints>"
end

#int_var(lower = nil, upper = nil, name = nil, start: nil, semi: false) ⇒ Variable

Declare an integer variable.

Bounds of exactly [0, 1] declare a :BINARY variable rather than an integer one — the same rule the Python and Julia clients apply, so the same model means the same thing whichever language wrote it.

With semi: true the variable is 0 or a whole number within its bounds, never in between: a delivery of either nothing or 10 to 25 units. Such a variable is called semi-integer. Its bounds must then be finite.

ship = m.int_var(10, 25, "ship", semi: true)   # none, or 10 to 25 units
m.minimize(2 * ship + 30 * ship.active)         # 2 per unit, 30 per delivery

Parameters:

  • semi (Boolean) (defaults to: false) —

    whether the variable may also be 0

Returns:

Raises:

  • (ArgumentError) —

    with semi, if a bound is missing or infinite



595
596
597
598
599
600
601
602
603
 
# File 'lib/quicopt/model.rb', line 595

def int_var(lower = nil, upper = nil, name = nil, start: nil, semi: false)
  lo = coerce_bound(lower, -Float::INFINITY)
  hi = coerce_bound(upper, Float::INFINITY)
  domain = if semi then :SEMIINTEGER
           elsif lo.zero? && hi == 1.0 then :BINARY
           else :INTEGER
           end
  declare(domain, lo, hi, name, start)
end

#intern(key) ⇒ 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 term stored under key, built by the block on first use, so that equal terms are one object.



811
812
813
 
# File 'lib/quicopt/model.rb', line 811

def intern(key)
  @interned[key] ||= yield
end

#lookup_table(name, values) ⇒ LookupTable

Declare a table of data that can be indexed by decisions. A model sometimes needs a number from a table at a position that is not known yet: the distance between the first and the second stop of a route whose ordering the service is still choosing, or the price of an option an integer variable picks. A Ruby array cannot be indexed this way; the table returned here can.

price  = m.lookup_table("price", [3.0, 1.0, 4.0, 1.5])
choice = m.int_var(0, 3, "choice")
m.minimize(price[choice])                   # picks option 1, at 1.0

Indexing with whole numbers only gives the entry itself; indexing with an expression, such as Permutation#item_at or an integer variable, gives an expression whose value is the entry at the positions the service chooses.

The whole table is sent with the model, so a very large table makes the request large.

Parameters:

  • name (String, Symbol) —

    the table's name; shares one namespace with the model's variables and permutations

  • values (Array<Numeric>, Array<Array<Numeric>>) —

    a vector (indexed table[i]) or a matrix (table[i, j], every row the same length) of numbers, none of them NaN

Returns:

Raises:

  • (TypeError) —

    if values is neither a vector nor a matrix of numbers

  • (ArgumentError) —

    if it is empty, ragged or holds NaN, or the name is taken



790
791
792
793
794
795
796
 
# File 'lib/quicopt/model.rb', line 790

def lookup_table(name, values)
  nm = claim(name)
  data, shape = table_data(nm, values)
  table = LookupTable.new(self, nm, data, shape)
  @tables << table
  @structured[nm] = table
end

#maximize(expr) ⇒ Expression

Maximize expr.

Returns:



825
826
827
 
# File 'lib/quicopt/model.rb', line 825

def maximize(expr)
  set_objective(expr, "max")
end

#minimize(expr) ⇒ Expression

Minimize expr.

Returns:



818
819
820
 
# File 'lib/quicopt/model.rb', line 818

def minimize(expr)
  set_objective(expr, "min")
end

#next_order ⇒ 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 order of the next read of a permutation, partition or lookup table, or of a term that switches: after every variable, then in the order they were first made.



803
804
805
 
# File 'lib/quicopt/model.rb', line 803

def next_order
  [1, @reads += 1]
end

#num_var(lower = nil, upper = nil, name = nil, start: nil, semi: false) ⇒ Variable

Declare a continuous variable.

With semi: true the variable is 0 or within its bounds, never in between: a shipment of either nothing or 2.5 to 8 tonnes. Such a variable is called semicontinuous. Its bounds must then be finite, and when 0 lies within them it is an ordinary variable.

Parameters:

  • lower (Numeric, nil) (defaults to: nil) —

    the lower bound; nil means unbounded below

  • upper (Numeric, nil) (defaults to: nil) —

    the upper bound; nil means unbounded above

  • name (String, nil) (defaults to: nil) —

    the variable's name; auto-generated when omitted

  • start (Numeric, nil) (defaults to: nil) —

    the starting point; defaults to 0 clamped into the bounds, matching the Python and Julia clients (to 0 with semi)

  • semi (Boolean) (defaults to: false) —

    whether the variable may also be 0

Returns:

Raises:

  • (ArgumentError) —

    with semi, if a bound is missing or infinite



575
576
577
 
# File 'lib/quicopt/model.rb', line 575

def num_var(lower = nil, upper = nil, name = nil, start: nil, semi: false)
  declare(semi ? :SEMICONTINUOUS : :CONTINUOUS, lower, upper, name, start)
end

#partition(name, n_items, n_parts, start: nil) ⇒ Partition

Declare an assignment of n_items items to n_parts parts as a decision: which team each person joins, which truck each parcel rides in. Items and parts are both numbered from 0, and a part may stay empty.

Six players of strengths 7, 5, 4, 3, 2 and 1 form a team of four and a team of two, as evenly matched as possible:

strength = [7, 5, 4, 3, 2, 1]                  # of players 0 to 5
m = Quicopt::Model.new
teams = m.partition("teams", 6, 2)             # 6 players into teams 0 and 1
total = (0...2).map { |t| (0...6).sum { |p| strength[p] * Quicopt.holds(teams.part_of(p) == t) } }
m.add(teams.size_of(0) == 4)                   # team 0 has four players
m.minimize(Quicopt.max(total[0], total[1]))

result = Quicopt::Client.new.solve(m)
result.objective                               # 11.0
result.structures["teams"].part_of             # [1, 0, 1, 0, 0, 0]: players 0 and 2 form team 1

Parameters:

  • name (String, Symbol) —

    identifies the partition in the result, as result.structures[name]; shares one namespace with the model's variables, permutations and lookup tables

  • n_items (Integer) —

    the number of items, at least 1

  • n_parts (Integer) —

    the number of parts, at least 2

  • start (Array<Integer>, nil) (defaults to: nil) —

    the assignment the service's search starts from: start[i] is the part of item i, one of 0...n_parts. Left out, item i starts in part i % n_parts.

Returns:

Raises:

  • (TypeError) —

    if n_items or n_parts is not an Integer

  • (ArgumentError) —

    if n_items is below 1, n_parts below 2, the name is taken, or start does not give each item a part



699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
 
# File 'lib/quicopt/model.rb', line 699

def partition(name, n_items, n_parts, start: nil)
  unless n_items.is_a?(Integer)
    raise TypeError, "a partition's number of items is a whole number, got #{n_items.inspect}"
  end
  unless n_parts.is_a?(Integer)
    raise TypeError, "a partition's number of parts is a whole number, got #{n_parts.inspect}"
  end
  raise ArgumentError, "a partition has at least 1 item, got #{n_items}" if n_items < 1
  raise ArgumentError, "a partition has at least 2 parts, got #{n_parts}" if n_parts < 2

  nm = claim(name)
  unless start.nil? || (start.is_a?(Array) && start.size == n_items &&
                        start.all? { |b| b.is_a?(Integer) && b >= 0 && b < n_parts })
    raise ArgumentError, "partition #{nm.inspect}: start gives each of the #{n_items} items a part " \
                         "from 0 to #{n_parts - 1}"
  end
  partition = Partition.new(self, nm, n_items, n_parts, start&.dup)
  @partitions << partition
  @structured[nm] = partition
end

#permutation(name, n_items, start: nil) ⇒ Permutation

Declare an ordering as a decision: n_items items placed in as many slots, one item per slot, both numbered from 0. For a route the items are the stops and the slots are the visits, so slot 0 holds the first stop visited; for a machine the items are the jobs and the slots the positions in its queue.

Five stops along a road; find the shortest route through all of them that visits stop 3 before stop 0:

position = [0, 3, 1, 4, 2]                  # km along the road, stops 0 to 4
m = Quicopt::Model.new
dist  = m.lookup_table("dist", position.map { |a| position.map { |b| (a - b).abs } })
route = m.permutation("route", 5)
route.precede(3, 0)                         # stop 3 is visited before stop 0
m.minimize((0...4).sum { |k| dist[route.item_at(k), route.item_at(k + 1)] })

result = Quicopt::Client.new.solve(m)
result.objective                            # 4.0
result.structures["route"].item_at          # [3, 1, 4, 2, 0]: the stops in the order visited

A model with a permutation is solved by a search, so its result has the status "heuristic".

Parameters:

  • name (String, Symbol) —

    identifies the permutation in the result, as result.structures[name]; shares one namespace with the model's variables and lookup tables

  • n_items (Integer) —

    the number of items, at least 2

  • start (Array<Integer>, nil) (defaults to: nil) —

    the arrangement the service's search starts from: start[i] is the slot of item i, so it holds each of 0...n_items once. Left out, item i starts in slot i.

Returns:

Raises:

  • (TypeError) —

    if n_items is not an Integer

  • (ArgumentError) —

    if n_items is below 2, the name is taken, or start is not an arrangement of 0...n_items



653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
 
# File 'lib/quicopt/model.rb', line 653

def permutation(name, n_items, start: nil)
  unless n_items.is_a?(Integer)
    raise TypeError, "a permutation's number of items is a whole number, got #{n_items.inspect}"
  end
  raise ArgumentError, "a permutation has at least 2 items, got #{n_items}" if n_items < 2

  nm = claim(name)
  unless start.nil? || (start.is_a?(Array) && start.all?(Integer) && start.sort == (0...n_items).to_a)
    raise ArgumentError, "permutation #{nm.inspect}: start must hold each of 0 to #{n_items - 1} once " \
                         "(start[i] is the slot item i starts in)"
  end
  permutation = Permutation.new(self, nm, n_items, start&.dup)
  @permutations << permutation
  @structured[nm] = permutation
end

#to_program ⇒ Quicopt::Modeler::V1::Program

Turn this model into the structured message the service reads.

Returns:

  • (Quicopt::Modeler::V1::Program) 


855
856
857
 
# File 'lib/quicopt/model.rb', line 855

def to_program
  Wire.program(self)
end

#to_s ⇒ Object

Renders the whole model: objective, rows, then declarations.



867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
 
# File 'lib/quicopt/model.rb', line 867

def to_s
  lines = ["#{@sense} #{@objective}"]
  lines << "subject to" unless @constraints.empty?
  @constraints.each { |c| lines << "  #{c}" }
  @variables.each do |v|
    range = "[#{Format.number(v.lower)}, #{Format.number(v.upper)}]"
    range = "{0} ∪ #{range}" if %i[SEMICONTINUOUS SEMIINTEGER].include?(v.domain)
    lines << "  #{v.name} in #{v.domain} #{range}"
  end
  @permutations.each do |p|
    rules = p.precedences.map { |a, b| "#{a} before #{b}" }
    rules = rules.empty? ? "" : ", with #{rules.join(', ')}"
    lines << "  #{p.name} is an ordering of items 0 to #{p.n_items - 1}#{rules}"
  end
  @partitions.each { |p| lines << "  #{p.name} puts items 0 to #{p.n_items - 1} in parts 0 to #{p.n_parts - 1}" }
  @tables.each { |t| lines << "  #{t.name} is a #{t.shape.join(' × ')} lookup table" }
  @blocks.each { |b| lines << "  #{b.name} is a block of #{b.variables.join(', ')}" }
  lines.join("\n")
end

#variable(name) ⇒ Variable?

Look a variable up by name.

Returns:



615
616
617
 
# File 'lib/quicopt/model.rb', line 615

def variable(name)
  @by_name[name.to_s]
end