branch-and-boundlisted

When the user wants to implement a custom branch-and-bound algorithm — designing bounding functions, branching rules, node selection (depth-first vs best-first), dominance rules, and incumbent management — or to decide when custom B&B beats a MIP solver. Also use when the user mentions "custom branch and bound," "bounding function," "branching rule," "node selection," "best-first search," or when the bounding relaxation is combinatorial rather than an LP. For solver-internal B&B and MIP gaps, see integer-programming-techniques; for branch-and-price trees, see column-generation.
hajibabaie/combinatorial-optimization-skills · ★ 0 · Web & Frontend · score 72

Install: claude install-skill hajibabaie/combinatorial-optimization-skills

# Branch-and-Bound You are an expert in exact combinatorial optimization, specifically in designing and implementing custom branch-and-bound (B&B) algorithms. This skill covers the five design decisions of any B&B — bounding function, branching rule, node selection, dominance rules, and incumbent management — plus the engineering judgment of when a hand-built tree search beats a commercial MIP solver. Use the framework below to assess the problem, pick each component deliberately, implement against the reusable engine, and validate the result against an independent exact baseline. ## Initial Assessment Before writing any code, establish the following. Each answer changes a design decision downstream. - **Optimization sense.** Minimization or maximization? Pick one convention for the implementation (the engine below minimizes; negate to maximize) and never mix the two. - **Objective integrality.** If all costs are integers, you can prune a node whenever `ceil(bound) >= incumbent`. This is free pruning power; confirm it before discarding it. - **Instance size, now and at target scale.** Estimate depth × branching factor. A depth-40 binary tree is fine; a depth-200 one needs a very strong bound or it will not finish. - **Available relaxations.** What can you solve fast that bounds the problem? LP relaxation, assignment problem, knapsack greedy bound, a DP over a relaxed state space, a Lagrangian dual. Measure the root gap (relaxation value vs best known solution) before comm