Seven items, each with a cost \(c_j\) and a weight \(w_j\), and two resources that the chosen items must supply: \(\min\ c^\top x\) subject to \(a_1^\top x \ge 8\), \(a_2^\top x \ge 7\), \(w^\top x \le 13\), \(x \in \{0,1\}^7\). Moving the two demands into the objective with multipliers \(\lambda \ge 0\) leaves a knapsack, and \(L(\lambda) = \min_x\, c^\top x + \lambda^\top (b - Ax)\) is the minimum of one plane per point of the knapsack: a concave polyhedral roof, whose top bounds the problem from below (\(\max L = 14.8 \le 17\), the gap of the relaxation). A bundle method climbs it knowing only the plane of each point it evaluates, a cutting plane, and keeps their minimum as a model.
Sette oggetti, ciascuno con un costo \(c_j\) e un peso \(w_j\), e due risorse che gli oggetti scelti devono fornire: \(\min\ c^\top x\) con \(a_1^\top x \ge 8\), \(a_2^\top x \ge 7\), \(w^\top x \le 13\), \(x \in \{0,1\}^7\). Portando le due domande nell'obiettivo con moltiplicatori \(\lambda \ge 0\) resta uno zaino, e \(L(\lambda) = \min_x\, c^\top x + \lambda^\top (b - Ax)\) è il minimo di un piano per ogni punto dello zaino: un tetto poliedrico concavo, la cui cima limita il problema dal basso (\(\max L = 14.8 \le 17\), il gap del rilassamento). Un metodo bundle lo scala conoscendo solo il piano di ogni punto che valuta, un piano di taglio, e ne tiene il minimo come modello.
\(c = (5, 9, 4, 6, 8, 4, 9)\), \(a_1 = (2, 3, 4, 2, 2, 0, 4)\), \(a_2 = (0, 4, 3, 2, 0, 4, 2)\), \(w = (5, 3, 3, 4, 2, 2, 2)\), \(\lambda \in [0, 3]^2\)
The roof as a relief on a square block, the side being the square of the multipliers: the dual function, or the model of the bundle at the step shown above; the path of the trial points is engraved as a groove with a pit at each point, and the dual optimum stands up as a small cone.
Il tetto come rilievo su un blocco quadrato, il cui lato è il quadrato dei moltiplicatori: la funzione duale, o il modello del bundle al passo mostrato sopra; il cammino dei punti di prova è inciso come un solco con una fossetta in ogni punto, e l'ottimo duale sporge come un piccolo cono.