Combinatorial auction
Class: BIP · Links: set packing by rows · Script: python/fam10_2_auction.py
Difficulty: ★☆☆☆☆ · Time: 20–30 min
Problem 10.2
An auctioneer has a set \(S = \{1, 2, \dots, n\}\) of \(n \in \mathbb{Z}_{\ge 1}\) items to sell and has received \(r \in \mathbb{Z}_{\ge 1}\) bids. For every bid \(j \in \{1, 2, \dots, r\}\), the set \(B_j \subseteq S\) is the subset of items requested and \(p_j \in \mathbb{Q}_{>0}\) the profit in euros if the bid is accepted. Every item can be sold at most once, and a bid can be accepted only if all its items are available. The auctioneer wants to choose a set of bids of maximum total profit.
The problem in words. We decide which bids to accept. The objective: maximum profit. The constraint: two accepted bids cannot ask for the same item. A bid is all-or-nothing: no part of it is accepted.
Model
Variables. A single family of \(r\) binaries: \(x_j \in \{0,1\}\) equals \(1\) if bid \(j\) is accepted.
Description. The objective adds up the profits of the accepted bids. It is a pure set packing: one constraint per item (\(n\) linear constraints) and one variable per bid. The constraint of item \(i\) says that the item is sold at most once, and hence that two bids competing for it cannot both be accepted.
By rows, not by pairs
An alternative, and worse, way of writing the same constraint is to list all the pairs of conflicting bids: \(x_j + x_{j'} \le 1\) for every \(j \ne j'\) with \(B_j \cap B_{j'} \ne \emptyset\). On the instance that would be nine constraints instead of four, and on real instances the number of pairs grows like \(r^2\) while the per-item constraints stay \(n\). The row form is also tighter: if three bids all ask for item \(i\), the row constraint says \(x_1 + x_2 + x_3 \le 1\), whereas the three pairwise inequalities admit \(x_1 = x_2 = x_3 = 1/2\).
The model in gurobipy
m = gp.Model("auction")
x = m.addVars(r, vtype=GRB.BINARY, name="x")
m.setObjective(gp.quicksum(p[j] * x[j] for j in range(r)), GRB.MAXIMIZE)
m.addConstrs((gp.quicksum(x[j] for j in range(r) if i in B[j]) <= 1
for i in range(n)), name="item")
The instance
\(n = 4\) items, \(r = 6\) bids.
| \(j=1\) | \(j=2\) | \(j=3\) | \(j=4\) | \(j=5\) | \(j=6\) | |
|---|---|---|---|---|---|---|
| \(B_j\) | \(\{1\}\) | \(\{2\}\) | \(\{3,4\}\) | \(\{1,3\}\) | \(\{2,4\}\) | \(\{1,3,4\}\) |
| \(p_j\) | 6 | 3 | 12 | 12 | 10 | 16 |
Written out, the model of the instance is
subject to
with \(x_j \in \{0,1\}\).
The model written on the data of the instance:
Constructive heuristic: the primal bound
The problem is a maximisation, so the heuristic gives the primal bound, which sits below the optimum. The bids are sorted by decreasing profit per item and those whose items are still free are accepted. The running time is \(O(r \log r + r\, n)\).
On the instance the ratios are \(6\), \(3\), \(6\), \(6\), \(5\) and \(16/3 \approx 5.33\), so the order is \(1, 3, 4, 6, 5, 2\):
- bid 1 \(\{1\}\): accepted (profit 6);
- bid 3 \(\{3,4\}\): accepted (profit 12);
- bid 4 \(\{1,3\}\): rejected, items \(1\) and \(3\) are already sold;
- bid 6 \(\{1,3,4\}\): rejected;
- bid 5 \(\{2,4\}\): rejected, item \(4\) is already sold;
- bid 2 \(\{2\}\): accepted (profit 3).
Bids \(1, 2, 3\) are accepted: \(z(\mathit{MILP}) \ge \mathit{LB} = 21\).
LP relaxation and dual: the dual bound
Associate a non-negative dual variable \(\lambda_i\) with each item constraint.
The same dual, written on the data of the instance:
Description. \(\lambda_i\) is the price the auctioneer puts on item \(i\). The objective is the total value of the lots at those prices. The constraints are the columns of the \(x_j\), one per bid: the items bid \(j\) asks for, priced at those values, must be worth at least what the bid pays. In short, no bid may turn out to be a bargain.
Recipe. Spread the profit of every bid over its items and take, for each item, the maximum over the bids that ask for it,
Feasibility is immediate: for every bid \(j\),
On the instance \(\bar\lambda = (6, 5, 6, 6)\) and \(z(\mathit{MILP}) \le \mathit{UB} = 23\).
A coarse recipe costs a lot
The "obvious" recipe \(\bar\lambda_i = \max_{j :\, i \in B_j} p_j\) (without dividing by \(|B_j|\)) is feasible too, but gives \(16 + 10 + 16 + 16 = 58\): more than twice as much. Dividing by the cardinality of the requested set is what makes the bound useful. It is worth trying several recipes and keeping the best: they are all valid, not all informative.
Optimal solution
At the optimum bids \(4\) (\(\{1,3\}\), profit \(12\)) and \(5\) (\(\{2,4\}\), profit \(10\)) are accepted: all four items are sold.
| \(LB\) (heuristic) | \(z(\mathit{MILP})\) | \(z(\mathit{LP})\) | \(z(\mathit{LP}^+)\) | \(UB\) (dual) | heuristic gap |
|---|---|---|---|---|---|
| 21 | 22 | 22 | 22 | 23 | \(4.5\%\) |
The auctioneer sells everything, but not because a constraint forces it: the constraints are \(\le\), not \(=\). With other bids the optimal solution might leave items on the shelf.
Additional considerations
- The valid inequalities \(x_j \le 1\) are implied by the item constraints whenever \(B_j \ne \emptyset\): indeed \(z(\mathit{LP}) = z(\mathit{LP}^+) = 22\).
- On this instance one also has \(z(\mathit{LP}) = z(\mathit{MILP})\): the relaxation lands on an integer vertex. That is luck, not a property of set packing. The minimal counterexample is the triangle: three items and three bids asking for two each, all of profit \(1\). There \(z(\mathit{LP}) = 3/2\) (with \(x = 1/2\) on all three) against \(z(\mathit{MILP}) = 1\).
- Set packing is NP-hard in general, but becomes easy when the incidence matrix is perfect or balanced. The triangle is the smallest non-perfect graph in this sense, and it is why clique inequalities are the classical cuts for this family.
Additional modelling questions
10.2.1 — Bids from the same participant
Bids \(4\) and \(5\) come from the same participant, who may win at most one of them. How does the model change? What is the new optimum?
A worked variant: limited deliveries
In this round the auctioneer can deliver at most two items in total.
One adds the single linear constraint
in which the coefficient of every bid is the number of items it asks for: it is a knapsack constraint laid on top of the set packing. On the instance the optimum drops to \(12\): a single two-item bid is accepted, the more profitable between bid \(3\) and bid \(4\) (both worth \(12\)).
The cap on the items delivered, \(\sum_j |B_j| x_j \le 2\), adds to the dual a \(\mu \ge 0\) with right-hand side \(2\), and in the column of every bid it appears multiplied by how many items that bid asks for. With \(\mu\) fixed, every bid spreads over its items net of \(\mu\) and \(\lambda_i\) is the largest among the bids asking for item \(i\): trying \(\mu\) among the per-item profits one reaches \(\mu = 6\), \(\lambda = 0\) and \(\ub = 12\). The heuristic accepts bid \(3\) alone and is worth \(12\) as well: the sandwich closes, and the optimum is known without solving the MILP.
| value | what it is | |
|---|---|---|
| \(\mathit{UB}\) | \(12\) | dual certificate built by hand |
| \(\mathit{LB}\) | \(12\) | heuristic solution |
| \(z(\mathit{LP})\) | \(12\) | relaxation without the bounds |
| \(z(\mathit{LP}^+)\) | \(12\) | relaxation with the bounds |
| \(z(\mathit{MILP})\) | \(12\) | optimum of the MILP |
Code
Complete script —
python/fam10_2_auction.py
(reproducible with python3 python/fam10_2_auction.py from the python/
folder). Notebook —
notebooks/fam10_2_auction.ipynb
— which opens in Colab from the badge at the top of the page.
Show the complete script — python/fam10_2_auction.py (275 lines)
"""Problem 10.2 -- Combinatorial auction (set packing).
An auctioneer has n items and receives r bids: bid j asks for the subset B_j and
pays p_j, and it is all or nothing. This is pure set packing: one constraint per
item, one variable per bid. Since it is a maximisation, the heuristic gives the
lower bound and the hand-built dual the upper one: the roles swap with respect to
10.1 and 10.2.
"""
import gurobipy as gp
import pandas as pd
from gurobipy import GRB
from mip import (ammissibile, dualita_forte, due_rilassamenti, frazione,
nuovo_modello, registra_bound, rilassamenti, risolvi, stampa_lp,
valuta)
from stile import ARANCIO, GRIGIO, TEAL, intestazione, plt, salva_dati, salva_figura
from esteso import salva_modello
R = range
# ---------- 1. MODEL AND INSTANCE ----------
intestazione("10.2 Combinatorial auction: choosing the bids of maximum profit")
n3 = 4 # items for sale
B3 = [[0], [1], [2, 3], [0, 2], [1, 3], [0, 2, 3]] # items asked by each bid
p3 = [6, 3, 12, 12, 10, 16] # profit of the bid
r3 = len(p3)
salva_dati(pd.DataFrame({"bid": [j + 1 for j in R(r3)],
"items": ["{" + ",".join(str(i + 1) for i in B3[j]) + "}"
for j in R(r3)],
"profit": p3}), "fam10_2_dati")
def modello_3(n, B, p, extra=None):
r = len(p)
m = nuovo_modello("auction")
x = m.addVars(r, vtype=GRB.BINARY, name="x") # 1 if the bid is accepted
m.setObjective(gp.quicksum(p[j] * x[j] for j in R(r)), GRB.MAXIMIZE)
m.addConstrs((gp.quicksum(x[j] for j in R(r) if i in B[j]) <= 1 for i in R(n)),
name="item")
return m, x
def duale_3(n, B, p):
"""min sum_i lam_i s.t. sum_{i in B_j} lam_i >= p_j for every bid j, lam >= 0.
The dual has one variable per item: lam_i is the price the auctioneer puts on
item i, and every bid must cost at least what it pays.
"""
r = len(p)
dl = nuovo_modello("dual_auction")
lam = dl.addVars(n, name="lam")
dl.setObjective(gp.quicksum(lam[i] for i in R(n)), GRB.MINIMIZE)
dl.addConstrs((gp.quicksum(lam[i] for i in B[j]) >= p[j] for j in R(r)), name="bid")
return dl, lam
m3, x3 = modello_3(n3, B3, p3)
salva_modello(m3, "fam10_2_primale")
print(" The model of the instance:")
stampa_lp(m3)
# ---------- 2. THE LP RELAXATION ----------
zlp3, zlp3r, _ = rilassamenti(m3)
# ---------- 3. THE DUAL OF THE RELAXATION (UPPER BOUND: IT IS A MAXIMUM) ----------
dl3, lam3 = duale_3(n3, B3, p3)
salva_modello(dl3, "fam10_2_duale")
# Hand recipe: spread every bid over its items and take the maximum,
# lam_i = max_{j : i in B_j} p_j / |B_j|. It is always feasible because for every
# bid j we have sum_{i in B_j} lam_i >= |B_j| * p_j / |B_j| = p_j.
mano = {f"lam[{i}]": max(p3[j] / len(B3[j]) for j in R(r3) if i in B3[j]) for i in R(n3)}
ub3, viol = valuta(dl3, mano)
assert viol <= 1e-9, viol
print(" Hand-built dual: lam_i = max_{j : i in B_j} p_j / |B_j| (the profit of every bid")
print(" spread over its items; the sum over B_j is then at least p_j):")
for i in R(n3):
quote = ", ".join(f"{p3[j]}/{len(B3[j])}" for j in R(r3) if i in B3[j])
print(f" item {i + 1}: max({quote}) = {frazione(mano[f'lam[{i}]'])}")
print(f" ub = sum of the prices = {frazione(ub3)}")
# for comparison: the recipe of the source notes, lam_i = max p_j over the bids
grezza = {f"lam[{i}]": max(p3[j] for j in R(r3) if i in B3[j]) for i in R(n3)}
ub_grezzo, viol_g = valuta(dl3, grezza)
assert viol_g <= 1e-9
print(f" (with the cruder recipe lam_i = max_j p_j one would only get "
f"{frazione(ub_grezzo)})")
dualita_forte(dl3, zlp3)
# ---------- 4. CONSTRUCTIVE HEURISTIC (LOWER BOUND: IT IS A MAXIMUM) ----------
# constructive heuristic on the profit per item: the most profitable bids are accepted among those
# whose items are still free. Cost O(r log r + r n).
def euristica(n, B, p):
r = len(p)
x = [0] * r
libero = [True] * n
passi = []
for j in sorted(R(r), key=lambda j: (-p[j] / len(B[j]), j)):
oggetti = "{" + ",".join(str(i + 1) for i in B[j]) + "}"
occupati = [i + 1 for i in B[j] if not libero[i]]
if occupati:
passi.append(f"bid {j + 1} {oggetti}, {p[j] / len(B[j]):.4g} per item: "
f"rejected, items {occupati} are already sold")
continue
x[j] = 1
for i in B[j]:
libero[i] = False
passi.append(f"bid {j + 1} {oggetti}, {p[j] / len(B[j]):.4g} per item: "
f"accepted (profit {p[j]})")
return x, passi
x_eur, passi = euristica(n3, B3, p3)
for k, riga in enumerate(passi, 1):
print(f" Step {k}. {riga}")
lb3 = sum(p3[j] * x_eur[j] for j in R(r3))
sol_eur = {f"x[{j}]": x_eur[j] for j in R(r3)}
assert ammissibile(m3, sol_eur), sol_eur
accettate = [j + 1 for j in R(r3) if x_eur[j]]
print(f" Heuristic solution: bids {accettate} lb = {frazione(lb3)}")
# ---------- 5. OPTIMUM OF THE MILP ----------
z3 = risolvi(m3)
ottime = [j + 1 for j in R(r3) if x3[j].X > 0.5]
venduti = sorted({i + 1 for j in R(r3) if x3[j].X > 0.5 for i in B3[j]})
print(f" Optimal solution: bids {ottime}, items sold {venduti}, profit {frazione(z3)}")
invenduti = [i + 1 for i in R(n3) if i + 1 not in venduti]
print(f" Unsold items: {invenduti if invenduti else 'none'}. The auctioneer sells everything,")
print(" but not because a constraint forces it: the constraints are <=, not =. With other")
print(" bids the optimal solution could leave items on the shelf.")
riga = registra_bound("3 auction", ub3, lb3, zlp3, zlp3r, z3, senso="max")
salva_dati(pd.DataFrame([riga]), "fam10_2_bound")
assert lb3 <= z3 <= zlp3r <= zlp3 <= ub3 + 1e-9
# ---------- 6. THE TWO RELAXATIONS AND INTEGRALITY ----------
intestazione("10.2 The two relaxations and the integrality of the relaxation")
print(f" z(LP) = {frazione(zlp3)} and z(LP+) = {frazione(zlp3r)} coincide: the constraints")
print(" sum_{j : i in B_j} x_j <= 1 already imply x_j <= 1 for every bid with a non-empty")
print(" B_j. The valid inequalities x_j <= 1 are therefore redundant and do not strengthen.")
assert abs(zlp3 - zlp3r) <= 1e-9
print(f" On this instance we also have z(LP) = z(MILP) = {frazione(z3)}: the relaxation")
print(" lands on an integer vertex. That is a lucky feature of the instance, not a property")
print(" of set packing. The minimal counterexample is the triangle: three items and three")
print(" bids asking for two of them each, all with profit 1.")
m_tri, _ = modello_3(3, [[0, 1], [1, 2], [0, 2]], [1, 1, 1])
dl_tri, _ = duale_3(3, [[0, 1], [1, 2], [0, 2]], [1, 1, 1])
z_tri = risolvi(m_tri)
zlp_tri, zlp_tri_r, _ = due_rilassamenti(m_tri, dl_tri)
print(f" Triangle: z(LP) = {frazione(zlp_tri)} (x = 1/2 on all three) against "
f"z(MILP) = {frazione(z_tri)}.")
assert zlp_tri > z_tri + 1e-9
salva_dati(pd.DataFrame([{"instance": "auction 10.2", "z_lp": zlp3, "z_milp": z3},
{"instance": "triangle", "z_lp": zlp_tri, "z_milp": z_tri}]),
"fam10_2_triangolo")
# ---------- 7. ADDITIONAL MODELLING QUESTIONS ----------
varianti = {}
def variante(nome, m):
z = risolvi(m)
print(f" {nome:70s} z = {frazione(z)}")
return z
# 3a: bids 4 and 5 come from the same bidder, who can win at most one
m, x = modello_3(n3, B3, p3)
m.addConstr(x[3] + x[4] <= 1, name="same_bidder")
varianti["2a"] = variante("2a. Bids 4 and 5 are from the same bidder (x4+x5 <= 1)", m)
# 3b: the auctioneer delivers at most two items in this round
m, x = modello_3(n3, B3, p3)
m.addConstr(gp.quicksum(len(B3[j]) * x[j] for j in R(r3)) <= 2, name="deliveries")
varianti["2b"] = variante("2b. At most two items are delivered (sum_j |B_j| x_j <= 2)", m)
salva_dati(pd.DataFrame({"variant": list(varianti), "z": list(varianti.values())}),
"fam10_2_varianti")
# ---------- 8. THE SANDWICH ON THE VARIANT 3b ----------
intestazione("10.2b The sandwich on the variant: at most two items delivered")
MAX_OGG = 2
def modello_3b(n, B, p, massimo=MAX_OGG):
mm, xx = modello_3(n, B, p)
mm.addConstr(gp.quicksum(len(B[j]) * xx[j] for j in R(len(p))) <= massimo, name="consegne")
return mm, xx
def duale_3b(n, B, p, massimo=MAX_OGG):
"""To the dual of 10.2 one adds mu >= 0 for the constraint sum_j |B_j| x_j <= 2.
The right-hand side is 2, so mu enters the objective, and in the column of
every bid it appears multiplied by how many items that bid asks for."""
rr = len(p)
dl = nuovo_modello("duale_asta_3b")
lam = dl.addVars(n, name="lam")
mu = dl.addVar(name="mu")
dl.setObjective(lam.sum() + massimo * mu, GRB.MINIMIZE)
dl.addConstrs((gp.quicksum(lam[i] for i in B[j]) + len(B[j]) * mu >= p[j] for j in R(rr)),
name="rc_x")
return dl
m3b, x3b = modello_3b(n3, B3, p3)
salva_modello(m3b, "fam10_2b_primale")
# -- feasible heuristic: the best bid that does not exceed the two items is taken --
print("Constructive heuristic: the bids in decreasing order of profit; a bid is accepted if")
print("its items are free and the total delivered stays within two.")
presi, consegnati, valore_3b = set(), 0, 0
for j in sorted(R(r3), key=lambda j: -p3[j]):
if consegnati + len(B3[j]) > MAX_OGG:
continue
if any(i in presi for i in B3[j]):
continue
presi |= set(B3[j])
consegnati += len(B3[j])
valore_3b += p3[j]
print(f" bid {j + 1} (items {sorted(i + 1 for i in B3[j])}, profit {p3[j]}): "
f"accepted, delivered {consegnati}")
lb3b = valore_3b
accettate_3b = [j for j in R(r3) if set(B3[j]) <= presi and len(B3[j]) <= MAX_OGG]
sol_3b = {f"x[{j}]": 0 for j in R(r3)}
presi2, cons2 = set(), 0
for j in sorted(R(r3), key=lambda j: -p3[j]):
if cons2 + len(B3[j]) <= MAX_OGG and not (set(B3[j]) & presi2):
sol_3b[f"x[{j}]"] = 1
presi2 |= set(B3[j]); cons2 += len(B3[j])
assert ammissibile(m3b, sol_3b), "the heuristic solution of the variant must be feasible"
print(f" lb = {frazione(lb3b)}")
# -- dual certificate: mu is paid twice and discounts every bid --
dl3b = duale_3b(n3, B3, p3)
salva_modello(dl3b, "fam10_2b_duale")
def valore_duale_3b(mu_val):
lam_v = {i: max([0.0] + [(p3[j] - len(B3[j]) * mu_val) / len(B3[j])
for j in R(r3) if i in B3[j]]) for i in R(n3)}
return sum(lam_v.values()) + MAX_OGG * mu_val, lam_v
candidati_3b = sorted({0.0} | {p3[j] / len(B3[j]) for j in R(r3)})
scelto_3b = min(candidati_3b, key=lambda v: valore_duale_3b(v)[0])
ub3b, lam_3b = valore_duale_3b(scelto_3b)
mano_3b = {f"lam[{i}]": lam_3b[i] for i in R(n3)} | {"mu": scelto_3b}
ub3b_val, viol_3b = valuta(dl3b, mano_3b)
assert viol_3b <= 1e-9, (viol_3b, mano_3b)
print("Dual solution by hand: with mu fixed, every bid is spread over its items net of mu,")
print(" and lam_i is the largest among the bids asking for item i. mu is tried among the")
print(" per-item profits of the bids and the lowest value is kept:")
print(f" mu = {frazione(scelto_3b)}, lam = {[frazione(lam_3b[i]) for i in R(n3)]}")
print(f" -> ub = {frazione(ub3b_val)}")
zlp3b, zlp3br, _ = due_rilassamenti(m3b, dl3b)
z3b = risolvi(m3b)
riga_3b = registra_bound("2b at most two items", ub3b_val, lb3b, zlp3b, zlp3br, z3b, senso="max")
salva_dati(pd.DataFrame([riga_3b]), "fam10_2b_bound")
assert lb3b <= z3b <= zlp3b + 1e-9 <= ub3b_val + 1e-9
# ---------- 9. FIGURE ----------
fig, ax = plt.subplots(figsize=(6.8, 3.2))
idx = list(R(r3))
colori = [TEAL if x3[j].X > 0.5 else GRIGIO for j in idx]
ax.bar(idx, p3, 0.55, color=colori)
for j in idx:
if x_eur[j]:
ax.plot(j, p3[j] + 0.6, marker="v", color=ARANCIO, ms=8)
ax.plot([], [], marker="v", ls="", color=ARANCIO, label="chosen by the heuristic")
ax.bar([], [], color=TEAL, label="accepted at the optimum")
ax.bar([], [], color=GRIGIO, label="rejected at the optimum")
ax.set_xticks(idx)
ax.set_xticklabels(["{" + ",".join(str(i + 1) for i in B3[j]) + "}" for j in idx])
ax.set_xlabel("items asked by the bid")
ax.set_ylabel("profit")
ax.set_title(f"10.2: heuristic {frazione(lb3)} <= optimum {frazione(z3)} <= dual "
f"{frazione(ub3)}")
ax.legend(fontsize=8, loc="upper left")
salva_figura(fig, "cap10_asta_offerte")
print("Done.")