Some decisions are an arrangement: an ordering, such as the stops of a
courier's route or the jobs on a machine, or a one-to-one assignment, such
as which department moves into which office. perm_var() declares such a
decision, a permutation.
Arguments
- m
A
model().- name
The permutation's name, unique within the model.
- n_items
How many items, and so how many slots; at least 2.
- start
The arrangement the service's search starts from:
start[i]is the slot of itemi, sostartcontains each of the numbers 1 ton_itemsonce. LeftNULL, itemistarts in sloti.
Value
The permutation, for use with item_at(), slot_of() and
precede().
add_perm_var() returns the model, invisibly.
Items and slots
A permutation arranges things, called items, in numbered places, called
slots, with exactly one item in each slot and one slot for each item.
Items and slots are both numbered from 1 to n_items. What they stand for
depends on the problem:
for a route, the items are the stops and the slots are the visits: slot 1 is the first stop visited, slot 2 the second, and so on;
for a machine, the items are the jobs and the slots are the positions in the queue;
for an office plan, the items are the departments and the slots are the offices.
item_at() gives the item in a slot, and slot_of() the slot of an item.
Both are expressions whose values the service chooses, like the value of a
decision variable. Data that depends on the arrangement, such as the
distance between consecutive stops, is read from a lookup_table():
dist[item_at(1:4, route), item_at(2:5, route)] is the length of each of
the four legs of a five-stop route.
precede() requires one item to be in an earlier slot than another, such
as a pickup before its delivery.
The answer
For each permutation, the result of solve() holds both directions under
res$structures$<name>: item_at, the item in each slot (for a route, the
stops in the order they are visited), and slot_of, the slot of each item.
set_start(), evaluate() and resample() take the arrangement from a
result too.
A model with a permutation is solved by a search, so its status is
"heuristic". Permutations can be combined with random variables, for
example a route whose travel times are uncertain, minimized in
expectation(). vignette("permutations", package = "quicopt") works
through two examples.
add_perm_var() declares the permutation in the same way but returns the
model, for use in a pipe; m$name then retrieves the permutation.
Examples
# Five stops along a road. Find the shortest route through all of them
# that visits stop 4 before stop 1.
position <- c(0, 3, 1, 4, 2) # km along the road, stops 1 to 5
m <- model()
dist <- lookup_table(m, "dist", abs(outer(position, position, "-")))
route <- perm_var(m, "route", 5)
precede(route, 4, 1) # stop 4 is visited before stop 1
minimize(m, sum(dist[item_at(1:4, route), item_at(2:5, route)]))
if (FALSE) { # \dontrun{
res <- solve(m)
res$structures$route$item_at # the stops in the order visited
} # }