Deliveries, fees and teams

A delivery of nothing, or of 10 to 25 units

A customer needs 40 units. Three suppliers can deliver them, but each one delivers either nothing or between 10 and 25 units, because smaller loads are not worth a trip. Each charges a price per unit and a fixed fee for every delivery it makes:

From which suppliers should the customer order, and how much from each?

A variable that is either 0 or between its bounds is declared with semi = TRUE. Its bounds are then the smallest and the largest delivery:

m <- model()
delivery <- int_var(m, "delivery", lower = 10, upper = 25, length = 3, semi = TRUE)

delivery[1] can be 0, 10, 11, …, 25, but not 5. The fee is due only for a delivery that takes place, which is what active() expresses: active(x) is 1 when x is not 0, and 0 when it is.

price <- c(1, 2, 3)
fee   <- c(30, 10, 5)
minimize(m, sum(price * delivery) + sum(fee * active(delivery)))
add(m, sum(delivery) >= 40)                      # the customer needs 40 units

res <- solve(m)
res$solution
#> delivery[1] delivery[2] delivery[3] 
#>          25          15           0
res$objective
#> [1] 95
res$status
#> [1] "optimal"

The customer orders 25 units from supplier 1 and 15 from supplier 2, for a total of 25 + 30 + 2 × 15 + 10 = 95. Supplier 3 has the smallest fee but the highest price, and it is not used. The status "optimal" means that no other order is cheaper: a model like this one, linear except for semi = TRUE and active(), is solved to a proven optimum.

Warehouses that supply several customers

Three warehouses supply three customers, who need 40, 30 and 20 units. Every delivery is again either nothing or 10 to 25 units, it costs a price per unit that depends on the distance, plus 5 for the trip. A warehouse that delivers anything has to be opened, for a fee:

demand  <- c(40, 30, 20)                                # units, customers 1 to 3
price   <- rbind(c(1, 3, 4),                            # price per unit, from warehouse 1
                 c(3, 1, 3),                            #                 from warehouse 2
                 c(4, 2, 1))                            #                 from warehouse 3
opening <- c(60, 50, 40)                                # fee for opening warehouses 1 to 3

There are nine possible deliveries, one from each warehouse to each customer. They are numbered so that deliveries 1 to 3 go to customer 1, from warehouses 1, 2 and 3, deliveries 4 to 6 to customer 2, and so on. Two small functions pick out the deliveries to one customer and from one warehouse:

m <- model()
ship <- int_var(m, "ship", lower = 10, upper = 25, length = 9, semi = TRUE)
to   <- function(c) ship[3 * (c - 1) + 1:3]             # to customer c, from warehouses 1 to 3
from <- function(w) ship[w + c(0, 3, 6)]                # from warehouse w, to customers 1 to 3

The deliveries to one customer form a small problem of their own: together they have to meet that customer’s demand. block() says so. It names the variables of one such subproblem, and a constraint on the variables of a single block holds in every solution the service returns:

for (c in 1:3) {
  block(m, paste0("customer_", c), to(c))
  add(m, sum(to(c)) >= demand[c])
}

The customers are linked only through the warehouses: a warehouse is opened once, however many customers it supplies. Its fee is due when it sends at least one unit, which holds() expresses: holds(sent >= 1) is 1 for a warehouse that sends anything and 0 for one that sends nothing.

sent <- c(sum(from(1)), sum(from(2)), sum(from(3)))     # units leaving each warehouse
minimize(m, sum(as.vector(price) * ship)                # price per unit
            + 5 * sum(active(ship))                     # 5 per delivery
            + sum(opening * holds(sent >= 1)))          # the fee of each warehouse in use

as.vector(price) lists the prices column by column, which is the order of the deliveries: from warehouses 1, 2 and 3 to customer 1 first.

res <- solve(m)
res$objective
#> [1] 300
matrix(res$solution, nrow = 3, dimnames = list(warehouse = 1:3, customer = 1:3))
#>          customer
#> warehouse  1  2  3
#>         1 25 10  0
#>         2  0  0  0
#>         3 15 20 20

Warehouse 2 stays closed. Warehouse 1 sends 25 units to customer 1 and 10 to customer 2, and warehouse 3 sends the rest. The total of 300 is 175 for the units, 25 for five deliveries and 100 for opening warehouses 1 and 3. The status of a model with holds() is "heuristic": a good answer, not a proven optimum.

res$status
#> [1] "heuristic"

Splitting into teams

Six players, of strengths 7, 5, 4, 3, 2 and 1, form a team of four and a team of two. The teams should be as evenly matched as possible, so the stronger team should be as weak as it can be.

Dividing things into groups is a decision of its own, a partition: each item goes into exactly one of several groups, called parts. part_var() declares it. part_of(i, teams) is the part of item i, and size_of(t, teams) is how many items part t holds; both are expressions whose values the service chooses.

strength <- c(7, 5, 4, 3, 2, 1)                         # of players 1 to 6
m <- model()
teams <- part_var(m, "teams", 6, 2)                     # 6 players into teams 1 and 2
add(m, size_of(1, teams) == 4)                          # team 1 has four players

The strength of a team is the sum of the strengths of its players. holds(part_of(1:6, teams) == t) is 1 for each player in team t and 0 for the others, so multiplying it by strength and adding up gives the strength of team t:

in_team <- function(t) holds(part_of(1:6, teams) == t)
minimize(m, max(sum(strength * in_team(1)), sum(strength * in_team(2))))

res <- solve(m)
res$objective
#> [1] 11
res$structures$teams$part_of
#> [1] 2 1 2 1 1 1
res$structures$teams$size_of
#> [1] 4 2

part_of lists the team of each player: players 1 and 3 form team 2, with strength 7 + 4 = 11, and the other four form team 1, with 5 + 3 + 2 + 1 = 11. The strengths add up to 22, so neither team can be weaker than 11, and this split is as even as a split can be.

More about these

• num_var(..., semi = TRUE) declares a continuous quantity that is 0 or between its bounds, such as a load measured in tonnes. Both bounds must be finite.
• A variable can be in one block at most, and a variable in a block needs finite bounds. Declaring blocks changes nothing else about a model.
• part_var(m, "teams", 6, 2, start = ...) sets the division the solve starts from, and set_start() takes it from an earlier result. evaluate() and resample() keep a partition fixed at the division in a result.
• solve(m, time_limit = 60) gives a model like the warehouses or the teams 60 seconds, which can find a better answer for a large model.