Lesson 22.7 — Formulations: PBQP and integer linear programming¶
Techniques: PBQP-based allocation (Scholz–Eckstein; LLVM
RegAllocPBQP); ILP-based allocation (Goodwin–Wilken; Appel–George optimal spilling) · Lab: none; theory, drills and real tools (llc -regalloc=pbqp, the HiGHS solver) · Prerequisites: Lessons 22.1–22.4 · Time: 3–4 hours
Colouring and linear scan are algorithms for register allocation. This lesson takes the other road: write register allocation down as an optimization problem in a standard form, and hand it to a solver. Two forms matter. PBQP (partitioned Boolean quadratic programming) gives every value a vector of costs, one per register or "spill", and every pair of values a matrix of costs for each combination of choices. It expresses irregular register files, pre-colouring and coalescing preferences naturally, and a reduction-based solver solves most real instances optimally [SE02]; LLVM ships it. 0-1 integer linear programming states the same choices as binary variables with linear constraints; it gives proven optima at a compile-time cost that production compilers do not pay, but it is the yardstick against which heuristics are measured [GW96, AG01].
1. Problem and motivation¶
Input: the values, their interferences and affinities, spill costs, and the machine's registers and constraints. Output: for each value a register or "spilled", minimizing total spill and copy cost. The motivation is irregularity: on DSPs and embedded processors, instructions accept only some registers for some operands, registers pair up, and some operations are cheaper in some registers. Graph colouring treats all colours alike; bolting constraints onto it gives heuristics on top of heuristics. An optimization formulation puts every such preference into the cost function.
PBQP¶
Scholz and Eckstein formulated register allocation for irregular architectures as PBQP and solved it with a reduction algorithm that is optimal whenever the graph can be reduced with nodes of degree at most two, and heuristic otherwise [SE02]. Hames and Scholz refined the heuristic and showed nearly optimal results on real code [HS06]. LLVM's RegAllocPBQP implements this design (llc -regalloc=pbqp), with its own heuristic for the non-optimal step [LLVM-PBQPRA].
ILP-based allocation¶
Goodwin and Wilken wrote global register allocation, including spill placement, copy elimination, rematerialization and callee/caller-saved decisions, as a 0-1 integer program, and solved it to optimality for many functions of their benchmarks, at compile times far beyond those of heuristic allocators [GW96]. Appel and George split the problem: first solve optimal spilling (where to spill and reload so that at most \(K\) values are live at every point) as an ILP, then colour the result with iterated coalescing, a decomposition aimed at x86 and its few registers [AG01].
2. Definitions and algorithms¶
PBQP¶
Definition 22.7.1 (PBQP instance)
A PBQP instance is a graph \((V, E)\) where each node \(u\) must choose one option \(x_u \in \{0, \dots, m_u - 1\}\), with a cost vector \(\vec c_u \in (\mathbb{R} \cup \{\infty\})^{m_u}\), and each edge \(\{u, v\}\) has a cost matrix \(C_{uv} \in (\mathbb{R} \cup \{\infty\})^{m_u \times m_v}\) (with \(C_{vu} = C_{uv}^{\top}\)). The cost of a selection is
and the problem is to find a selection of minimum cost (\(\infty\) = infeasible).
Definition 22.7.2 (Register allocation as PBQP)
For a register class with registers \(r_0, \dots, r_{K-1}\), every value \(v\) has options numbered \(0\) (spill) and \(1 + j\) (register \(r_j\)). Its vector is \(\vec c_v = (\mathrm{cost}(v), p_0, \dots, p_{K-1})\), where \(p_j = \infty\) if \(v\) may not use \(r_j\) (pre-colouring, a call-crossing value and a caller-saved register, an instruction that only accepts some registers) and otherwise a small preference cost. An interference edge has \(C_{uv}[1 + j][1 + j'] = \infty\) whenever \(r_j \asymp r_{j'}\) (same or aliasing registers) and 0 elsewhere. An affinity of weight \(w\) has \(C_{uv}[1 + j][1 + j] = -w\) (a bonus for sharing a register) and 0 elsewhere. Edges between the same pair add up.
Algorithm 22.7.3 (PBQP by reduction, after [SE02])
- Input: a PBQP instance.
- Output: a selection \(x\) and its cost.
- Precondition: finite option sets; at least one finite-cost selection exists for the optimality claim.
- Postcondition: if no RN step was applied, \(x\) is optimal (Theorem 22.7.4).
- Invariant: the reduced instance plus the recorded reductions encode, for every selection of the remaining nodes, the minimum cost of extending it to the removed nodes.
function SolvePBQP(G):
stack ← []
while G has nodes:
if some node u has degree 0: # R0
push (R0, u); remove u
else if some node u has degree 1 with neighbour v: # RI
for each option j of v:
δ[j] ← min over i of ( c_u[i] + C_uv[i][j] ); choice_u[j] ← the argmin
c_v ← c_v + δ; push (RI, u, v, choice_u); remove u
else if some node u has degree 2 with neighbours v, w: # RII
for each option j of v, l of w:
D[j][l] ← min over i of ( c_u[i] + C_uv[i][j] + C_uw[i][l] )
choice_u[j][l] ← the argmin
C_vw ← C_vw + D (create the edge if absent); push (RII, u, v, w, choice_u); remove u
else: # RN (heuristic)
u ← a node of maximal degree (or by another heuristic)
i ← argmin over i of ( c_u[i] + Σ over neighbours v of min_j (C_uv[i][j] + c_v[j]) )
for each neighbour v: c_v[j] ← c_v[j] + C_uv[i][j] for all j
push (RN, u, i); remove u
for each entry, from the last pushed to the first: # back-propagation
(R0, u): x_u ← argmin c_u (with the vector as it was when u was removed)
(RI, u, v, ch): x_u ← ch[x_v]
(RII, u, v, w, ch): x_u ← ch[x_v][x_w]
(RN, u, i): x_u ← i
return x, cost(x)
The drill oracle (regalloc.pbqp_reduce) picks, among the nodes of smallest degree (with
degrees \(\ge 3\) treated alike), the first by name; ties among options go to the lowest.
Theorem 22.7.4 (R0, RI and RII are exact)
Each of R0, RI and RII transforms an instance \(P\) into an instance \(P'\) with one node fewer such that the optimal cost of \(P'\) equals that of \(P\), and back-propagation turns an optimal selection of \(P'\) into an optimal selection of \(P\). Hence if Algorithm 22.7.3 applies no RN step, it returns an optimal selection.
Proof
RI. Fix any selection \(y\) of the nodes other than \(u\). The cost of \(P\) with \(y\) and a choice \(i\) for \(u\) is \(\mathrm{cost}_{-u}(y) + \vec c_u[i] + C_{uv}[i][y_v]\), where \(\mathrm{cost}_{-u}\) collects all terms not involving \(u\) (\(u\)'s only edge is to \(v\)). The best \(i\) gives \(\mathrm{cost}_{-u}(y) + \delta[y_v]\), which is exactly the cost of \(y\) in \(P'\) (where \(\delta\) was added to \(\vec c_v\)). So \(\min_P = \min_y \mathrm{cost}_{P'}(y) = \min_{P'}\), and choosing \(x_u = \mathrm{choice}_u[y_v]\) attains it. RII. The same argument with the two edges of \(u\): the terms involving \(u\) are \(\vec c_u[i] + C_{uv}[i][y_v] + C_{uw}[i][y_w]\), whose minimum over \(i\) is \(D[y_v][y_w]\), added to the edge \(v - w\). R0. A node without edges contributes \(\vec c_u[x_u]\) independently of everything else; the best option is \(\arg\min \vec c_u\). By induction over the reductions (the last reduced node is solved first), back-propagation yields a selection whose cost equals the optimum of \(P\). RN fixes \(u\)'s option by a local estimate, which can be wrong (§3), so optimality is lost after the first RN step.
Theorem 22.7.5 (PBQP is NP-hard)
Deciding whether a PBQP instance has a selection of cost 0 is NP-complete, even with all entries in \(\{0, \infty\}\) and three options per node.
Proof
In NP: check a selection. Hardness: from 3-colourability. Give each node of a graph three options with cost vector \((0, 0, 0)\) and each edge the matrix with \(\infty\) on the diagonal and 0 elsewhere; a finite-cost (cost 0) selection is exactly a proper 3-colouring (Theorem 22.3.6). The reduction also shows that PBQP generalizes register allocation without spilling, so no polynomial exact algorithm is expected.
ILP-based allocation¶
Definition 22.7.6 (A 0-1 ILP for assignment with spilling and copies)
With values \(V\), registers \(r_0, \dots, r_{K-1}\) of one class, interference edges \(E\) and affinities \(A\) (with weights \(w_{uv}\)), use binary variables \(x_{v,r}\) (\(v\) in register \(r\)), \(s_v\) (\(v\) spilled) and \(d_{uv}\) (the copy between \(u\) and \(v\) remains). Minimize
subject to
Goodwin and Wilken's formulation is richer: variables per program point decide where each value is loaded, stored and kept, so that live ranges can be split optimally [GW96]. Appel and George's optimal-spilling ILP has variables per instruction (value \(v\) in a register / in memory / loaded / stored at point \(p\)) and the constraint "at most \(K\) values in registers at each point", without assigning registers [AG01].
Algorithm 22.7.7 (Allocation by ILP, and the Appel–George decomposition)
- Input: the formulation of Definition 22.7.6 (or of [AG01]); an ILP solver.
- Output: an optimal assignment for the model.
- Precondition: the instance fits the solver's limits (time, size).
- Postcondition: the returned assignment is valid and of minimum objective value (Theorem 22.7.8).
- Invariant: the solver's branch-and-bound keeps an incumbent (best known feasible solution) and a lower bound; it stops when they meet.
function AllocateByILP(F, K):
build variables and constraints of Definition 22.7.6
(x, s, d) ← SolveILP(minimize objective) # branch and bound / cut
return { v ↦ r | x[v][r] = 1 } ∪ { v ↦ spill | s[v] = 1 }
function AppelGeorge(F, K):
S ← SolveILP(optimal spilling: at most K values in registers at each point)
F' ← insert S's loads and stores into F # now MaxLive ≤ K everywhere
return IteratedCoalescing(F', K) # Algorithm 22.4.6; may add moves
Theorem 22.7.8 (The ILP captures the allocation problem)
The feasible solutions of the ILP of Definition 22.7.6 are exactly the valid assignments (Definition 22.1.6) of a uniform machine with the given constraints, and the objective equals the spill cost of the spilled values plus the weight of the affinities whose ends are not in the same register, where exactly one spilled end counts as "not the same" and two spilled ends count as the same. Hence an optimal ILP solution is an optimal assignment in this model.
Proof
The first constraint gives every value exactly one location. The second forbids two interfering values in the same register, for every register: validity (ii). The last one encodes (iii) and (iv). Conversely a valid assignment sets \(x\) and \(s\) accordingly and satisfies the constraints. For an affinity \(\{u, v\}\), if both are in the same register \(r\) then every difference \(x_{u,r'} - x_{v,r'}\) is 0 and \(d_{uv} = 0\) is feasible (and optimal, since \(w_{uv} > 0\)). If exactly one end is in a register \(r\), one of the two differences at \(r\) is 1 and forces \(d_{uv} = 1\); if they are in different registers, both are. If both ends are spilled, \(d_{uv} = 0\): the model treats a copy between two spilled values as removable (they may share a stack slot). So the objective is the spill cost plus the weight of the remaining register copies and reloads.
3. Worked example¶
PBQP¶
A small instance from the pbqp drill (./course drill pbqp --seed 1 --difficulty hard), with options (spill, r0, r1):
flowchart LR
a((a)) -. move .- b((b))
b --- c((c))
c --- d((d))
a -. move .- dVectors: \(\vec c_a = (3, 0, 0)\), \(\vec c_b = (2, 1, 1)\), \(\vec c_c = (5, 1, 0)\), \(\vec c_d = (2, 1, 0)\). The move edges \(a - b\) and \(a - d\) have \(-1\) for equal registers; the interference edges \(b - c\) and \(c - d\) have \(\infty\) for equal registers. Every node has degree 2, so reduction starts with RII:
| step | rule | node | effect |
|---|---|---|---|
| 1 | RII | a | new edge \(b - d\) with \(D[j][l] = \min_i (\vec c_a[i] + C_{ab}[i][j] + C_{ad}[i][l])\): \(D = \begin{pmatrix} 0 & -1 & -1 \\ -1 & -2 & -1 \\ -1 & -1 & -2 \end{pmatrix}\) (rows: \(b\)'s option, columns: \(d\)'s) |
| 2 | RII | b | \(b\) now has neighbours \(c\) and \(d\); new matrix on \(c - d\) (added to the interference matrix): \(\begin{pmatrix} 0 & -1 & -1 \\ 0 & 0 & -1 \\ 0 & -1 & 0 \end{pmatrix}\) |
| 3 | RI | c | \(c\) has only \(d\): \(\delta = (0, -1, 0)\), so \(\vec c_d = (2, 0, 0)\) |
| 4 | R0 | d | \(\arg\min (2, 0, 0) = 1\): \(d \mapsto r_0\) |
| 5 | back | c | \(\mathrm{choice}_c[x_d = 1] = 2\): \(c \mapsto r_1\) |
| 6 | back | b | \(\mathrm{choice}_b[x_c = 2][x_d = 1] = 1\): \(b \mapsto r_0\) |
| 7 | back | a | \(\mathrm{choice}_a[x_b = 1][x_d = 1] = 1\): \(a \mapsto r_0\) |
Total cost \(0 + 1 + 0 + 1 - 1 - 1 = 0\), which equals the brute-force minimum (Theorem 22.7.4: no RN step was needed). Both moves are coalesced (\(a\), \(b\), \(d\) in \(r_0\)) at the price of \(b\) and \(d\) taking their slightly more expensive register.
When RN is needed. On the running example with \(K = 3\), a and i have degree 7 and 6 and the graph cannot be reduced by R0–RII alone. With spill costs as vectors and the loop moves as \(-10\) bonuses, the oracle's RN step fixes a to a register by its local estimate, and the solution then spills c (cost 20) and coalesces both loop moves: objective \(20 - 20 = 0\). The optimum, by exhaustive search, spills a (13) and also coalesces both moves: \(13 - 20 = -7\). A single heuristic decision lost 7 units.
Try it
./course drill pbqp --seed 3 --difficulty medium --solution shows a tree-shaped instance
reduced by RI steps only.
ILP-based allocation¶
The same running example as the ILP of Definition 22.7.6 with \(K = 3\) (spill costs from Lesson 22.3; affinities i–i2 and s–s2 with weight 10, s–a with weight 1): HiGHS finds the optimum 14 = spill a (13) + the entry copy s ← a (1), coalescing both loop copies; §7 shows the run. This is the solution IRC found in Lesson 22.4 and the SSA allocator in Lesson 22.6, now with a proof of optimality for this model.
4. Invariants and correctness¶
PBQP¶
Theorem 22.7.4 (exactness of R0/RI/RII) and Theorem 22.7.5 (NP-hardness) in §2. The invariant of Algorithm 22.7.3 is the one the proof of Theorem 22.7.4 uses: after each reduction, the instance's cost function, minimized over the removed nodes, equals the original one.
Infinite costs everywhere
With \(\infty\) entries, RI can produce an all-\(\infty\) vector: the instance has no finite solution (for example a value that must be in a caller-saved register and live across a call). Register-allocation instances always keep option 0 (spill) finite, which guarantees a finite solution; an instance built without a spill option can be infeasible.
ILP-based allocation¶
Theorem 22.7.8. Correctness of the output also depends on the solver: an ILP solver returns a solution proved optimal only if it terminates with a zero gap; production systems that use ILP set time limits and fall back to a heuristic, keeping the incumbent solution.
5. Complexity¶
\(n\) values, \(e\) edges, \(K\) registers (so vectors of length \(m = K + 1\)).
| Algorithm | Time (worst) | Time (typical) | Space | Justification |
|---|---|---|---|---|
| PBQP reductions R0/RI/RII | \(O(n \cdot m^3)\) | near-linear in \(n\) | \(O(e \cdot m^2)\) | RI: \(O(m^2)\); RII: \(O(m^3)\) (a min over \(m\) for each of \(m^2\) entries); each node is reduced once |
| PBQP exact | NP-hard (Theorem 22.7.5); \(O(m^n)\) brute force | — | — | |
| ILP (Definition 22.7.6) | exponential (branch and bound) | seconds to minutes per function [GW96] | \(O(nK + eK)\) variables and constraints | \(nK + n + \lvert A\rvert\) variables; \(n + eK + \lvert A\rvert K\) constraints |
| Appel–George optimal spilling | exponential in the worst case | practical on x86 functions [AG01] | \(O(N \cdot n)\) variables | one variable family per (point, value) |
Pathological family. For PBQP, a clique \(K_t\) of values: every node has degree \(t - 1\), so after the first RN step the remaining clique is still dense and every step is heuristic. For ILP, symmetric instances (all registers equivalent) make branch and bound explore \(K!\) equivalent permutations unless symmetry is broken, for example by requiring the \(j\)-th value of a clique to use a register \(\le j\).
6. Variants and refinements¶
PBQP¶
- Hames–Scholz heuristic. Choose the RN node by spill cost per degree and delay decisions for nodes that are conservatively allocatable [HS06]. Trade-off: closer to optimal, more bookkeeping; this is what LLVM's
RegAllocSolverImpl::reducedoes (§7). - Branch-and-bound PBQP for exact solutions on small graphs [HS06]. Trade-off: optimal, exponential worst case.
- SSA-based PBQP. On SSA the graph is chordal and PBQP can exploit a perfect elimination order for its reduction sequence [BZB11]. Trade-off: fewer heuristic steps.
ILP-based allocation¶
- Decomposition (Appel–George): optimal spilling by ILP, then assignment by colouring [AG01]. Trade-off: much smaller ILPs; assignment may add copies.
- Combinatorial allocation and scheduling (Unison) formulates allocation and instruction scheduling together with constraint programming [CCBS19]. Trade-off: the best code quality reported for the two problems together, compile times far beyond production budgets.
7. In real compilers¶
PBQP¶
LLVM builds a PBQP graph from the live intervals (RegAllocPBQP::initializeGraph in llvm/lib/CodeGen/RegAllocPBQP.cpp), with spill costs, interference matrices and, with -pbqp-coalescing, coalescing bonuses, and solves it with PBQP::RegAlloc::solve (llvm/include/llvm/CodeGen/RegAllocPBQP.h, RegAllocSolverImpl::reduce): locally optimal R0/R1/R2 first, then any "conservatively allocatable" node, then the node with the lowest spill cost per degree [LLVM-PBQPRA]. Spilled values get spill code and the process repeats, as in Chaitin's loop.
LLVM's PBQP allocator against greedy on a high-pressure loop
Reproduce (clang 23.1.2, llc 23.1.2; press.c from Lesson 22.3 §7):
clang-23 --target=x86_64-linux-gnu -O2 -fno-unroll-loops -fno-vectorize -S -emit-llvm press.c -o press-x86_64-linux-gnu.ll
for o in "-regalloc=greedy" "-regalloc=pbqp" "-regalloc=pbqp -pbqp-coalescing"; do
llc -O2 $o press-x86_64-linux-gnu.ll -o p.s
printf '%-34s spills %2d reloads %2d folded %2d moves %2d instructions %3d\n' "$o" \
$(grep -c ' Spill$' p.s) $(grep -c ' Reload$' p.s) $(grep -c 'Folded' p.s) \
$(grep -cE '^\s+movq\s+%r[a-z0-9]+, %r[a-z0-9]+$' p.s) $(grep -cE '^\s+[a-z]' p.s)
done
Output (complete):
-regalloc=greedy spills 12 reloads 11 folded 3 moves 7 instructions 106
-regalloc=pbqp spills 21 reloads 14 folded 19 moves 6 instructions 101
-regalloc=pbqp -pbqp-coalescing spills 21 reloads 14 folded 19 moves 5 instructions 100
What to notice: "spills" counts spill comments (folded ones included), "folded" the
spills and reloads merged into arithmetic instructions (addq (%rsp), %rax). PBQP produces
shorter code with more memory operands folded into instructions: x86's cheap memory operands
make "spill and fold" competitive, and PBQP's cost vectors do not model that the greedy
allocator's splitting keeps values in registers in the hot path. -pbqp-coalescing adds the
affinity bonuses of Definition 22.7.2 and removes one more register-to-register copy. PBQP is
not LLVM's default on any mainstream target; it exists for irregular register files.
ILP-based allocation¶
No mainstream production compiler allocates registers by ILP; the compile time is too high and unpredictable. ILP and constraint-programming allocators exist in research compilers [GW96, AG01, CCBS19] and serve as baselines for heuristics. The box below solves the running example with an off-the-shelf solver.
Optimal allocation of the running example with the HiGHS ILP solver
Reproduce (HiGHS 1.11.0 via highspy 1.11.0 from PyPI; Python 3.11+; uv fetches the
package into its cache):
cat > ilp.py <<'EOF'
# Optimal spilling + register assignment for the running example (Lesson 22.7),
# as a 0-1 ILP solved by HiGHS: K = 3 registers.
import highspy
V = ["a", "i", "s", "c", "t", "u", "s2", "i2", "r"]
cost = {"a": 13, "i": 50, "s": 21, "c": 20, "t": 20, "u": 20, "s2": 20, "i2": 20, "r": 2}
E = [("a","c"),("a","i"),("a","i2"),("a","s"),("a","s2"),("a","t"),("a","u"),("c","i"),
("c","s"),("i","s"),("i","s2"),("i","t"),("i","u"),("i2","s2")]
moves = [("i", "i2", 10), ("s", "s2", 10), ("s", "a", 1)] # phi copies, edge weights
K = 3
h = highspy.Highs(); h.setOptionValue("output_flag", False)
x = {(v, r): h.addBinary() for v in V for r in range(K)}
sp = {v: h.addBinary() for v in V}
d = {(p, q): h.addBinary() for p, q, _ in moves} # 1 if the copy remains
for v in V:
h.addConstr(sum(x[v, r] for r in range(K)) + sp[v] == 1)
for u, v in E:
for r in range(K):
h.addConstr(x[u, r] + x[v, r] <= 1)
for p, q, _ in moves:
for r in range(K):
h.addConstr(d[p, q] >= x[p, r] - x[q, r])
h.addConstr(d[p, q] >= x[q, r] - x[p, r])
h.minimize(sum(cost[v] * sp[v] for v in V) + sum(w * d[p, q] for p, q, w in moves))
print("status:", h.modelStatusToString(h.getModelStatus()), " objective:", h.getInfo().objective_function_value)
print("spilled:", [v for v in V if h.val(sp[v]) > 0.5])
print("registers:", {v: r for v in V for r in range(K) if h.val(x[v, r]) > 0.5})
print("remaining copies:", [(p, q) for p, q, _ in moves if h.val(d[p, q]) > 0.5])
EOF
uv run --no-project --with highspy==1.11.0 python ilp.py
Output (complete):
status: Optimal objective: 14.0
spilled: ['a']
registers: {'i': 0, 's': 2, 'c': 1, 't': 1, 'u': 2, 's2': 2, 'i2': 0, 'r': 2}
remaining copies: [('s', 'a')]
What to notice: the 14 interference edges are those of Lesson 22.1 §3, and the solver
proves (status Optimal) that spilling a and keeping s ← a is the cheapest solution
with 3 registers: 13 + 1. Both loop copies are coalesced (i/i2 in 0, s/s2 in 2),
the result of IRC in Lesson 22.4 and of SSA colouring in Lesson 22.6. The copy s ← a
counts because exactly one of its ends is spilled (Theorem 22.7.8). With 39 binary
variables this solves instantly; ILPs for real functions have thousands.
8. Comparison¶
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| PBQP (Scholz–Eckstein) | models irregular files, preferences, coalescing in one cost function; optimal when R0–RII suffice | \(O(n m^3)\) · slower than greedy in LLVM | near-optimal on irregular architectures [HS06]; on x86 more spills than greedy in the box above | moderate (reductions + back-propagation) | LLVM -regalloc=pbqp (DSP-like targets), research |
| ILP (Goodwin–Wilken; Appel–George) | provably optimal for its model | exponential · seconds to minutes per function | the best possible within the model | small model, large solver | research baselines, offline code generation |
Choose PBQP when the register file is irregular and constraints dominate (DSPs, pairs, banked registers). Choose ILP when you need the optimum as a benchmark, or can afford minutes per function (embedded firmware compiled once).
9. Assessment¶
- Quiz (
./course quiz 22):pbqp-rii-cost,pbqp-ri-exact,ilp-constraint,ilp-objective-running,appel-george-split(tagspbqp,ilp). - Drill:
./course drill pbqp(R0/RI/RII reductions, optimal selection). ILP has no drill: an ILP instance is solved by a solver, not traced by hand; the quiz asks for the constraints and the objective value on the running example instead. - Flashcards: tags
pbqp,ilp.
References¶
See the chapter references.