Integer Programming

Why Integer Programming Matters

A delivery vehicle can carry three units of weight. Two indivisible parcels each weigh two units and earn three units of profit. A continuous optimizer can suggest taking one parcel and half of the other, earning $4.5$. A real dispatch must take whole parcels, so its best profit is $3$. Integrality changes both the feasible decisions and the proof that a decision is best.

Integer programming (IP) models discrete decisions using integer variables. Binary variables express yes/no choices; general integers express counts. Together with linear objectives and constraints, these give integer linear programs and mixed-integer linear programs (MILPs). This lesson uses linear models throughout. Applications include selecting projects, assigning shifts, locating facilities, and choosing production quantities.

You will learn three related mechanisms: branch-and-bound partitions the integer choices while maintaining objective bounds; cutting planes strengthen a continuous relaxation using inequalities valid for the integer choices; branch-and-cut combines both inside one search. A complete two-parcel trace shows what each mechanism contributes. The programs implement an exact, bounded-size binary knapsack solver with an optional cover-based bound; the text also gives the general MILP control flow.

Matrix notation and asymptotic analysis are enough to begin. Reading the linear-programming lesson first helps explain relaxations, but no LP library is needed to run these examples.

Core Concepts and Terminology

A maximization MILP has a form such as $$ z^\star=\max\{c^\top x:Ax\le b,\ \ell\le x\le u,\ x_j\in\mathbb Z\text{ for }j\in I\}. $$ Here $A,b,c,\ell,u$ define a linear model, and $I$ identifies the variables required to be integers. Variables outside $I$ remain continuous. A pure integer model makes every variable integer; a binary model additionally restricts each variable to $0$ or $1$. Bounds and equalities may appear in other equivalent forms.

The LP relaxation replaces integrality by continuous values while retaining all linear constraints and bounds. Its feasible region contains every feasible integer decision. For maximization, a finite optimal relaxation value $U_{\mathrm{LP}}$ therefore satisfies $z^\star\le U_{\mathrm{LP}}$. A feasible integer solution $\hat x$ gives an incumbent value $L=c^\top\hat x\le z^\star$. Throughout this lesson lower means incumbent, upper means relaxation/search bound; minimization reverses these roles.

A node adds restrictions inherited along a search-tree path. Its upper bound applies only to its own remaining decisions. The frontier contains unprocessed subproblems. A global upper bound is $$ U=\max\bigl(\{L\}\cup\{U_v:v\text{ is on the frontier}\}\bigr), $$ where each $U_v$ is any valid cached upper bound for that node, even a bound inherited from its parent. The absolute gap is $U-L$. Equality certifies optimality; a positive gap records unresolved possibilities.

Our running binary knapsack model is $$ \max\ 3x_1+3x_2,\qquad 2x_1+2x_2\le3,\qquad x_1,x_2\in\{0,1\}. $$ The LP permits $x=(1,\tfrac12)$ and objective $\tfrac92$. Integer feasible points are $(0,0),(1,0),(0,1)$. Their best objective is $3$. Because this model has integer profits and binary variables, its objective is integer-valued, so $\lfloor\tfrac92\rfloor=4$ is already a valid integer upper bound. Such flooring needs an integer-valued objective; it is generally invalid for a MILP with continuous objective contributions.

A valid inequality holds for all integer feasible points. A cut is useful when it also excludes an unwanted fractional point. Both parcels together exceed capacity, so $x_1+x_2\le1$ is valid. It excludes $(1,\tfrac12)$ while retaining every feasible binary choice. The figure shows regions and objective values rather than a gradient trajectory: integer programming advances through bounds, cuts, and subproblems.

How Integer Programming Works, Step by Step

General branch-and-bound. Start with the original model at the root and an incumbent if one is known. Select a frontier node and solve its LP relaxation. An infeasible relaxation proves the node contains no feasible integer solution. A finite upper bound no better than the incumbent also permits pruning. If an optimal LP solution satisfies all required integrality conditions, it is a feasible model solution: update the incumbent if better, then fathom the node.

Otherwise choose an integer-constrained variable with fractional LP value $x_j^\star$. The two children impose $$ x_j\le\lfloor x_j^\star\rfloor \quad\text{and}\quad x_j\ge\lceil x_j^\star\rceil. $$ Every integer value belongs to exactly one branch. For a binary variable these children are simply $x_j=0$ and $x_j=1$. Child regions are subsets of their parent's region, so a parent's upper bound remains valid before either child LP is solved. Repeat until the frontier is closed or a resource limit stops the search.

Cutting planes. Before branching, a separator can identify valid inequalities violated by the current LP optimum. Add selected cuts and reoptimize the LP. A global cut must hold for every integer solution of the original model. A cut justified only by a node's branch restrictions is local to that node and its descendants. Adding valid cuts can reduce the maximization upper bound without creating children. Adding every possible cut is usually impractical; separation, selection, and LP reoptimization cost work too.

For binary knapsack, a set $\mathcal C$ is a cover when $$ \sum_{i\in\mathcal C}w_i\gt C. $$ Selecting all its members violates capacity, so the cover inequality is $$ \sum_{i\in\mathcal C}x_i\le\lvert\mathcal C\rvert-1. $$ A minimal cover ceases to be a cover if any one member is removed. Minimality improves the basic inequality's relevance, but is not needed for validity.

Generic branch-and-cut. At a selected node, solve the relaxation, check infeasibility and bounds, update the incumbent for an integer solution, and otherwise try a limited number of cut rounds. If useful cuts were added, return to the LP solve and repeat those checks. If no further cut round is chosen, branch on a fractional integer variable. The flowchart assumes finite node LP optima whenever feasible; an unbounded relaxation requires additional handling in a general solver. An unbounded relaxation alone does not establish that the integer model is unbounded.

Exact mechanism used in the programs. The implemented family is $$ \max\sum_{i=1}^n p_i x_i,\qquad \sum_{i=1}^n w_i x_i\le C,\qquad x_i\in\{0,1\}. $$ All profits are nonnegative and all weights are positive. At each node, solve its single-capacity LP by filling free items in descending density $p_i/w_i$, skipping fixed variables. Compare densities by cross multiplication to avoid floating-point ties. Ties use the original item index. The solution has at most one fractional item; keep the fully included prefix and omit the fractional item and everything after it to obtain a feasible candidate. This candidate is a heuristic for the integer problem, not an assumption of optimality.

If cuts are enabled, build one global cover before search: sort by decreasing weight, breaking ties by original index, then take the shortest prefix exceeding capacity. If even all items fit, no cover exists and this bound is disabled. The chosen prefix is minimal: removing its smallest item leaves the preceding feasible prefix; removing any larger item removes at least as much weight.

To keep the implementation independent of a general LP engine, compute a second relaxation using only that cover and variable fixings, dropping the capacity constraint. Suppose fixed-included items have profit $V$, and $a$ of them belong to $\mathcal C$. Let $F$ be the free items and $k=\lvert\mathcal C\rvert-1-a$. Its optimum is $$ U_{\mathrm{cover}} =V+\sum_{i\in F\setminus\mathcal C}p_i +\operatorname{TopSum}_k\{p_i:i\in F\cap\mathcal C\}, $$ where $\operatorname{TopSum}_k$ adds the largest at most $k$ available profits. Capacity-feasible nodes cannot have $k\lt0$: that would already include an overweight cover. Nonnegative profits make taking the largest allowed profits optimal for this cardinality relaxation.

Combine the two valid bounds as $$ U_v=\min\{\lfloor U_{\mathrm{LP}}\rfloor,U_{\mathrm{cover}}\}, $$ or use $\lfloor U_{\mathrm{LP}}\rfloor$ alone when the cover is disabled. This minimum need not equal the LP optimum with both constraints present. It is a valid, potentially weaker bound obtained from separate relaxations. The programs are cover-strengthened branch-and-bound; they do not implement generic cut separation and joint LP reoptimization.

The exact processing order is: pop a node, prune if its inherited bound is dominated, reject overweight fixed choices, compute bounds and a candidate, update the incumbent, then fathom or branch. Branch on the fractional item, assign the include child an ID first, and push exclude before include on a LIFO stack. Stop after at most node_cap processed nodes. Remaining children retain their parent's valid bound, so a stopped search can still report an honest global interval.

flowchart TD
    A["Initialize model, incumbent, frontier"] --> B{"Open node and budget?"}
    B -->|"No"| Z["Report incumbent and global bound"]
    B -->|"Yes"| C["Select node and solve LP"]
    C --> D{"LP infeasible or bound dominated?"}
    D -->|"Yes: fathom"| B
    D -->|"No"| E{"LP solution integer feasible?"}
    E -->|"Yes"| F["Update incumbent and fathom"]
    F --> B
    E -->|"No"| G{"Useful valid cut and cut budget?"}
    G -->|"Yes"| H["Add cuts with correct scope"]
    H --> C
    G -->|"No"| I["Branch on fractional integer variable"]
    I --> J["Queue children with inherited bounds"]
    J --> B

Worked Example with a Full Trace

Use weights $(2,2)$, profits $(3,3)$, capacity $3$, and descending-density ties broken by original index. Both densities are $3/2$, so item $1$ is considered first. The empty incumbent starts at $L=0$. Before any relaxation, the sum of all profits is a safe root bound of $6$.

Without the cover. The following is the full include-first depth-first run. A node fixes only the variables named; all other variables remain free. The incumbent becomes $(1,0)$ at the root and never changes afterward, because equal-value candidates do not replace it.

1. Node 0, root. Take item $1$ fully: remaining capacity $1$, whole profit $3$. Take half of item $2$ in the relaxation, so $x^{\mathrm{LP}}=(1,\tfrac12)$, $U_{\mathrm{LP}}=3+\tfrac12\cdot3=\tfrac92$, and integer upper bound $4$. The whole-prefix candidate $(1,0)$ is feasible and raises $L$ to $3$. Since $4\gt3$, branch on fractional $x_2$. Assign include child ID $1$ and exclude child ID $2$; both inherit upper bound $4$.
2. Node 1, $x_2=1$. Fixed weight is $2$ and fixed profit $3$. There is room for half of free item $1$, so $x^{\mathrm{LP}}=(\tfrac12,1)$, $U_{\mathrm{LP}}=\tfrac92$, upper bound $4$. The whole-prefix candidate $(0,1)$ has value $3$, tying the incumbent. Branch on $x_1$; children receive IDs $3$ and $4$, each with inherited bound $4$.
3. Node 3, $x_1=x_2=1$. Fixed weight is $4\gt3$, fixed profit is $6$. Reject the node without solving an LP. The value $6$ belongs to an infeasible choice and never becomes an incumbent. The valid incumbent remains $3$.
4. Node 4, $x_1=0,x_2=1$. Fixed weight is $2$, fixed profit $3$, and no free item remains. The LP optimum $(0,1)$ is integral with value $3$. Fathom the node; it cannot improve the incumbent.
5. Node 2, $x_2=0$. Free item $1$ fits fully. The LP optimum $(1,0)$ is integral with value $3$, so fathom. The frontier is empty: global $U=L=3$.

The run processes five nodes and solves four relaxations. A small implementation change that checks a newly computed bound before reporting integrality could label the last two nodes as bound-pruned instead; these programs deliberately report INTEGRAL first when their relaxation is integral.

With the cover. The descending-weight prefix is $\mathcal C=\{1,2\}$ because $2\le3$ but $2+2\gt3$. Its inequality $x_1+x_2\le1$ is violated by the root LP solution, whose left side is $3/2$. At the root $V=0$, $a=0$, $k=1$, and there are no non-cover items. Thus $U_{\mathrm{cover}}=3$ and $U_v=\min(4,3)=3$. The same feasible candidate gives $L=3$, so the root is fathomed by bound. One node and one LP suffice. In this particular model the joint cut LP also has value $3$, although the independent-bound construction does not guarantee such equality on other inputs.

Stop after one node without the cover. The root finds $(1,0)$ and branches, then the budget ends. Two unprocessed children still have cached upper bound $4$. Return NODE_LIMIT, incumbent value $3$, global upper bound $4$, and absolute gap $1$. It would be incorrect to report optimality just because the best solution found so far is feasible.

In every output line, L is the global incumbent after processing that node; U is that processed node's bound, not necessarily the global upper bound. Only the final result's upper combines all pending nodes. Node IDs record creation order, while step records processing order.

Implementation in Python, C++, and Java

All three programs use the same exact arithmetic, deterministic ordering, tree policy, and result fields. Copy a complete panel into main.py, main.cpp, or Main.java. Run with Python 3.10+, a C++17 compiler, or Java 8+ respectively. There is no random seed because the algorithm uses no randomness.

The supported input domain is $0\le n\le16$, integer weights $1\le w_i\le100$, integer profits $0\le p_i\le100$, integer capacity $0\le C\le1000$, a Boolean cut flag, and integer budget $0\le\texttt{node\_cap}\le200000$. Weight and profit vectors must have equal lengths. Invalid values raise ValueError or an invalid-argument exception. Python rejects Boolean coefficients and budgets rather than treating them as integers; C++ and Java take integer vectors through their static types. Python accepts lists and tuples; Java rejects null arrays.

A bit in fixed means its variable is assigned; the corresponding bit of chosen says whether that assignment is one. Unset fixed bits identify free variables. Bit positions and the stored branch index are zero-based; printed branch numbers and mathematical subscripts start at one. Returned cover indices are also zero-based. The best solution is decoded from best_mask.

The relaxation stores its bound as a reduced integer fraction lp_num/lp_den. Density comparisons and bound flooring use integers. Within this input domain, total profit is at most $1600$, a bound numerator is at most $160000$, ratio cross-products are at most $10000$, and all masks fit within $16$ bits, so C++ and Java arithmetic fits signed 32-bit integers. Enlarging the domain requires reviewing these bounds.

The zero vector is always feasible and the binary domain is finite, so these programs return only OPTIMAL or NODE_LIMIT. This family cannot be infeasible or unbounded. OPTIMAL means the returned feasible value equals the valid global upper bound, even if some dominated entries remain on the internal stack at a budget boundary. open_nodes counts only pending nodes whose cached bound still exceeds the incumbent.

For diagnostics, LP=NONE means no relaxation was solved, cut=OFF means no cover bound was evaluated, and U=NONE is the infeasible-node sentinel. Reduced integer LP values print with denominator one. Every processed node records an event; CACHED_BOUND discards a node using its inherited upper bound before a fresh feasibility or LP check. bound_calls counts actual relaxation evaluations. The sample prints the complete baseline trace, the cover-strengthened root, and the stopped-search certificate.

from dataclasses import dataclass
from functools import cmp_to_key
from math import gcd


@dataclass
class State:
    iteration: int
    node_id: int
    parent_id: int
    fixed: int
    chosen: int
    weight: int
    value: int
    action: str
    has_lp: bool
    lp_num: int
    lp_den: int
    cut_upper: int
    upper: int
    best_value: int
    best_mask: int
    branch: int


@dataclass
class Result:
    status: str
    best_mask: int
    value: int
    upper: int
    processed: int
    bound_calls: int
    open_nodes: int
    cover: list[int]
    history: list[State]


def solve(weights, profits, capacity, cuts=False, node_cap=200000):
    if not isinstance(weights, (list, tuple)) or not isinstance(profits, (list, tuple)):
        raise ValueError("weights and profits must be sequences")
    n = len(weights)
    integer = lambda x: type(x) is int
    if (len(profits) != n or n > 16
            or any(not integer(w) or not 1 <= w <= 100 for w in weights)
            or any(not integer(p) or not 0 <= p <= 100 for p in profits)
            or not integer(capacity) or not 0 <= capacity <= 1000
            or type(cuts) is not bool
            or not integer(node_cap) or not 0 <= node_cap <= 200000):
        raise ValueError("unsupported model or budget")

    def compare(i, j):
        a, b = profits[i] * weights[j], profits[j] * weights[i]
        return -1 if a > b else 1 if a < b else (i > j) - (i < j)

    order = sorted(range(n), key=cmp_to_key(compare))
    cover = []
    if cuts:
        total = 0
        for i in sorted(range(n), key=lambda i: (-weights[i], i)):
            cover.append(i)
            total += weights[i]
            if total > capacity:
                break
        if total <= capacity:
            cover = []
    cover_mask = sum(1 << i for i in cover)
    best, best_mask, calls, next_id = 0, 0, 0, 1
    # Node tuple: id, parent, fixed mask, chosen mask, weight, profit, upper.
    stack = [(0, -1, 0, 0, 0, 0, sum(profits))]
    history = []
    while stack and len(history) < node_cap:
        nid, parent, fixed, chosen, weight, value, cached = stack.pop()
        has_lp, num, den, cut_upper, branch = False, 0, 1, -1, -1
        upper = cached
        if cached <= best:
            action = "CACHED_BOUND"
        elif weight > capacity:
            upper, action = -1, "INFEASIBLE"
        else:
            calls += 1
            has_lp = True
            room, candidate, candidate_value = capacity - weight, chosen, value
            whole, fractional = value, -1
            for i in order:
                if fixed & (1 << i) or profits[i] == 0:
                    continue
                if weights[i] <= room:
                    room -= weights[i]
                    whole += profits[i]
                    candidate |= 1 << i
                    candidate_value += profits[i]
                elif room > 0:
                    fractional = i
                    break
                else:
                    break
            if fractional < 0:
                num, den = whole, 1
            else:
                den = weights[fractional]
                num = whole * den + room * profits[fractional]
                g = gcd(num, den)
                num, den = num // g, den // g
            upper = num // den
            if cover:
                slots = len(cover) - 1 - (chosen & cover_mask).bit_count()
                free_cover = sorted(
                    (profits[i] for i in cover if not fixed & (1 << i)),
                    reverse=True)
                cut_upper = value + sum(
                    profits[i] for i in range(n)
                    if not fixed & (1 << i) and not cover_mask & (1 << i))
                cut_upper += sum(free_cover[:slots])
                upper = min(upper, cut_upper)
            if candidate_value > best:
                best, best_mask = candidate_value, candidate
            if fractional < 0:
                action = "INTEGRAL"
            elif upper <= best:
                action = "BOUND"
            else:
                action, branch = "BRANCH", fractional
                bit = 1 << branch
                include = (next_id, nid, fixed | bit, chosen | bit,
                           weight + weights[branch], value + profits[branch], upper)
                exclude = (next_id + 1, nid, fixed | bit, chosen, weight, value, upper)
                next_id += 2
                stack.extend((exclude, include))
        history.append(State(len(history) + 1, nid, parent, fixed, chosen,
                             weight, value, action, has_lp, num, den, cut_upper,
                             upper, best, best_mask, branch))
    upper = max([best] + [node[6] for node in stack])
    open_nodes = sum(node[6] > best for node in stack)
    return Result("OPTIMAL" if upper == best else "NODE_LIMIT", best_mask, best,
                  upper, len(history), calls, open_nodes, cover, history)


def show(label, r, n):
    print(label)
    for s in r.history:
        lp = f"{s.lp_num}/{s.lp_den}" if s.has_lp else "NONE"
        cut = str(s.cut_upper) if s.cut_upper >= 0 else "OFF"
        upper = str(s.upper) if s.upper >= 0 else "NONE"
        branch = str(s.branch + 1) if s.branch >= 0 else "-"
        print(f"step={s.iteration} node={s.node_id} LP={lp} cut={cut} "
              f"U={upper} L={s.best_value} action={s.action} branch={branch}")
    x = ",".join(str((r.best_mask >> i) & 1) for i in range(n))
    print(f"{r.status} x=[{x}] value={r.value} upper={r.upper} "
          f"nodes={r.processed} LPs={r.bound_calls} open={r.open_nodes}")


if __name__ == "__main__":
    for label, cuts, cap in [("branch-and-bound", False, 100),
                             ("cover-strengthened", True, 100),
                             ("node-limit", False, 1)]:
        show(label, solve([2, 2], [3, 3], 3, cuts, cap), 2)

#include <algorithm>
#include <iostream>
#include <numeric>
#include <stdexcept>
#include <string>
#include <vector>
using namespace std;

struct State {
    int iteration, node_id, parent_id, fixed, chosen, weight, value;
    string action;
    bool has_lp;
    int lp_num, lp_den, cut_upper, upper, best_value, best_mask, branch;
};
struct Result {
    string status;
    int best_mask, value, upper, processed, bound_calls, open_nodes;
    vector<int> cover;
    vector<State> history;
};
struct Node {
    int id, parent, fixed, chosen, weight, value, upper;
};
int popcount(int mask) {
    int count = 0;
    while (mask) { mask &= mask - 1; ++count; }
    return count;
}
Result solve(const vector<int>& weights, const vector<int>& profits,
             int capacity, bool cuts = false, int node_cap = 200000) {
    int n = int(weights.size());
    if (profits.size() != weights.size() || n > 16 || capacity < 0
            || capacity > 1000 || node_cap < 0 || node_cap > 200000)
        throw invalid_argument("unsupported model or budget");
    for (int i = 0; i < n; ++i)
        if (weights[i] < 1 || weights[i] > 100 || profits[i] < 0 || profits[i] > 100)
            throw invalid_argument("unsupported coefficient");
    vector<int> order(n), cover;
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
        int a = profits[i] * weights[j], b = profits[j] * weights[i];
        return a != b ? a > b : i < j;
    });
    if (cuts) {
        vector<int> heavy(n); iota(heavy.begin(), heavy.end(), 0);
        sort(heavy.begin(), heavy.end(), [&](int i, int j) {
            return weights[i] != weights[j] ? weights[i] > weights[j] : i < j;
        });
        int total = 0;
        for (int i : heavy) {
            cover.push_back(i); total += weights[i];
            if (total > capacity) break;
        }
        if (total <= capacity) cover.clear();
    }
    int cover_mask = 0;
    for (int i : cover) cover_mask |= 1 << i;
    int best = 0, best_mask = 0, calls = 0, next_id = 1;
    vector<Node> stack;
    stack.push_back({0, -1, 0, 0, 0, 0, accumulate(profits.begin(), profits.end(), 0)});
    vector<State> history;
    while (!stack.empty() && int(history.size()) < node_cap) {
        Node node = stack.back(); stack.pop_back();
        int nid = node.id, parent = node.parent, fixed = node.fixed, chosen = node.chosen;
        int weight = node.weight, value = node.value, upper = node.upper;
        bool has_lp = false;
        int num = 0, den = 1, cut_upper = -1, branch = -1;
        string action;
        if (upper <= best) action = "CACHED_BOUND";
        else if (weight > capacity) { upper = -1; action = "INFEASIBLE"; }
        else {
            ++calls; has_lp = true;
            int room = capacity - weight, candidate = chosen, candidate_value = value;
            int whole = value, fractional = -1;
            for (int i : order) {
                if ((fixed & (1 << i)) || profits[i] == 0) continue;
                if (weights[i] <= room) {
                    room -= weights[i]; whole += profits[i];
                    candidate |= 1 << i; candidate_value += profits[i];
                } else if (room > 0) { fractional = i; break; }
                else break;
            }
            if (fractional < 0) { num = whole; den = 1; }
            else {
                den = weights[fractional]; num = whole * den + room * profits[fractional];
                int g = gcd(num, den); num /= g; den /= g;
            }
            upper = num / den;
            if (!cover.empty()) {
                int slots = int(cover.size()) - 1 - popcount(chosen & cover_mask);
                vector<int> free_cover;
                for (int i : cover) if (!(fixed & (1 << i))) free_cover.push_back(profits[i]);
                sort(free_cover.rbegin(), free_cover.rend());
                cut_upper = value;
                for (int i = 0; i < n; ++i)
                    if (!(fixed & (1 << i)) && !(cover_mask & (1 << i))) cut_upper += profits[i];
                for (int k = 0; k < slots && k < int(free_cover.size()); ++k)
                    cut_upper += free_cover[k];
                upper = min(upper, cut_upper);
            }
            if (candidate_value > best) { best = candidate_value; best_mask = candidate; }
            if (fractional < 0) action = "INTEGRAL";
            else if (upper <= best) action = "BOUND";
            else {
                action = "BRANCH"; branch = fractional;
                int bit = 1 << branch;
                Node include = {next_id, nid, fixed | bit, chosen | bit,
                                weight + weights[branch], value + profits[branch], upper};
                Node exclude = {next_id + 1, nid, fixed | bit, chosen, weight, value, upper};
                next_id += 2; stack.push_back(exclude); stack.push_back(include);
            }
        }
        history.push_back({int(history.size()) + 1, nid, parent, fixed, chosen, weight,
                           value, action, has_lp, num, den, cut_upper, upper, best, best_mask, branch});
    }
    int upper = best, open_nodes = 0;
    for (const Node& node : stack) {
        upper = max(upper, node.upper);
        if (node.upper > best) ++open_nodes;
    }
    return {upper == best ? "OPTIMAL" : "NODE_LIMIT", best_mask, best, upper,
            int(history.size()), calls, open_nodes, cover, history};
}
void show(const string& label, const Result& r, int n) {
    cout << label << '\n';
    for (const State& s : r.history) {
        string lp = s.has_lp ? to_string(s.lp_num) + "/" + to_string(s.lp_den) : "NONE";
        cout << "step=" << s.iteration << " node=" << s.node_id << " LP=" << lp
             << " cut=" << (s.cut_upper >= 0 ? to_string(s.cut_upper) : "OFF")
             << " U=" << (s.upper >= 0 ? to_string(s.upper) : "NONE")
             << " L=" << s.best_value << " action=" << s.action
             << " branch=" << (s.branch >= 0 ? to_string(s.branch + 1) : "-") << '\n';
    }
    cout << r.status << " x=[";
    for (int i = 0; i < n; ++i) { if (i) cout << ','; cout << ((r.best_mask >> i) & 1); }
    cout << "] value=" << r.value << " upper=" << r.upper << " nodes=" << r.processed
         << " LPs=" << r.bound_calls << " open=" << r.open_nodes << '\n';
}
int main() {
    vector<int> weights = {2, 2}, profits = {3, 3};
    show("branch-and-bound", solve(weights, profits, 3, false, 100), 2);
    show("cover-strengthened", solve(weights, profits, 3, true, 100), 2);
    show("node-limit", solve(weights, profits, 3, false, 1), 2);
    return 0;
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static class State {
        int iteration, node_id, parent_id, fixed, chosen, weight, value;
        String action;
        boolean has_lp;
        int lp_num, lp_den, cut_upper, upper, best_value, best_mask, branch;
        State(int iteration, int node_id, int parent_id, int fixed, int chosen,
              int weight, int value, String action, boolean has_lp, int lp_num,
              int lp_den, int cut_upper, int upper, int best_value, int best_mask, int branch) {
            this.iteration = iteration; this.node_id = node_id; this.parent_id = parent_id;
            this.fixed = fixed; this.chosen = chosen; this.weight = weight; this.value = value;
            this.action = action; this.has_lp = has_lp; this.lp_num = lp_num; this.lp_den = lp_den;
            this.cut_upper = cut_upper; this.upper = upper; this.best_value = best_value;
            this.best_mask = best_mask; this.branch = branch;
        }
    }
    static class Result {
        String status;
        int best_mask, value, upper, processed, bound_calls, open_nodes;
        List<Integer> cover;
        List<State> history;
        Result(String status, int best_mask, int value, int upper, int processed,
               int bound_calls, int open_nodes, List<Integer> cover, List<State> history) {
            this.status = status; this.best_mask = best_mask; this.value = value;
            this.upper = upper; this.processed = processed; this.bound_calls = bound_calls;
            this.open_nodes = open_nodes; this.cover = cover; this.history = history;
        }
    }
    static class Node {
        int id, parent, fixed, chosen, weight, value, upper;
        Node(int id, int parent, int fixed, int chosen, int weight, int value, int upper) {
            this.id = id; this.parent = parent; this.fixed = fixed; this.chosen = chosen;
            this.weight = weight; this.value = value; this.upper = upper;
        }
    }
    static int gcd(int a, int b) {
        while (b != 0) { int t = a % b; a = b; b = t; }
        return a;
    }
    static Result solve(int[] weights, int[] profits, int capacity, boolean cuts, int node_cap) {
        if (weights == null || profits == null || profits.length != weights.length
                || weights.length > 16 || capacity < 0 || capacity > 1000
                || node_cap < 0 || node_cap > 200000)
            throw new IllegalArgumentException("unsupported model or budget");
        int n = weights.length;
        for (int i = 0; i < n; ++i)
            if (weights[i] < 1 || weights[i] > 100 || profits[i] < 0 || profits[i] > 100)
                throw new IllegalArgumentException("unsupported coefficient");
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; ++i) order[i] = i;
        Arrays.sort(order, (i, j) -> {
            int a = profits[i] * weights[j], b = profits[j] * weights[i];
            return a != b ? Integer.compare(b, a) : Integer.compare(i, j);
        });
        List<Integer> cover = new ArrayList<>();
        if (cuts) {
            Integer[] heavy = order.clone();
            Arrays.sort(heavy, (i, j) -> weights[i] != weights[j]
                    ? Integer.compare(weights[j], weights[i]) : Integer.compare(i, j));
            int total = 0;
            for (int i : heavy) {
                cover.add(i); total += weights[i];
                if (total > capacity) break;
            }
            if (total <= capacity) cover.clear();
        }
        int cover_mask = 0, sum = 0;
        for (int i : cover) cover_mask |= 1 << i;
        for (int p : profits) sum += p;
        int best = 0, best_mask = 0, calls = 0, next_id = 1;
        List<Node> stack = new ArrayList<>();
        stack.add(new Node(0, -1, 0, 0, 0, 0, sum));
        List<State> history = new ArrayList<>();
        while (!stack.isEmpty() && history.size() < node_cap) {
            Node node = stack.remove(stack.size() - 1);
            int nid = node.id, parent = node.parent, fixed = node.fixed, chosen = node.chosen;
            int weight = node.weight, value = node.value, upper = node.upper;
            boolean has_lp = false;
            int num = 0, den = 1, cut_upper = -1, branch = -1;
            String action;
            if (upper <= best) action = "CACHED_BOUND";
            else if (weight > capacity) { upper = -1; action = "INFEASIBLE"; }
            else {
                ++calls; has_lp = true;
                int room = capacity - weight, candidate = chosen, candidate_value = value;
                int whole = value, fractional = -1;
                for (int i : order) {
                    if ((fixed & (1 << i)) != 0 || profits[i] == 0) continue;
                    if (weights[i] <= room) {
                        room -= weights[i]; whole += profits[i];
                        candidate |= 1 << i; candidate_value += profits[i];
                    } else if (room > 0) { fractional = i; break; }
                    else break;
                }
                if (fractional < 0) { num = whole; den = 1; }
                else {
                    den = weights[fractional]; num = whole * den + room * profits[fractional];
                    int g = gcd(num, den); num /= g; den /= g;
                }
                upper = num / den;
                if (!cover.isEmpty()) {
                    int slots = cover.size() - 1 - Integer.bitCount(chosen & cover_mask);
                    List<Integer> free_cover = new ArrayList<>();
                    for (int i : cover) if ((fixed & (1 << i)) == 0) free_cover.add(profits[i]);
                    free_cover.sort((a, b) -> Integer.compare(b, a));
                    cut_upper = value;
                    for (int i = 0; i < n; ++i)
                        if ((fixed & (1 << i)) == 0 && (cover_mask & (1 << i)) == 0)
                            cut_upper += profits[i];
                    for (int k = 0; k < slots && k < free_cover.size(); ++k)
                        cut_upper += free_cover.get(k);
                    upper = Math.min(upper, cut_upper);
                }
                if (candidate_value > best) { best = candidate_value; best_mask = candidate; }
                if (fractional < 0) action = "INTEGRAL";
                else if (upper <= best) action = "BOUND";
                else {
                    action = "BRANCH"; branch = fractional;
                    int bit = 1 << branch;
                    Node include = new Node(next_id, nid, fixed | bit, chosen | bit,
                            weight + weights[branch], value + profits[branch], upper);
                    Node exclude = new Node(next_id + 1, nid, fixed | bit, chosen, weight, value, upper);
                    next_id += 2; stack.add(exclude); stack.add(include);
                }
            }
            history.add(new State(history.size() + 1, nid, parent, fixed, chosen, weight,
                    value, action, has_lp, num, den, cut_upper, upper, best, best_mask, branch));
        }
        int upper = best, open_nodes = 0;
        for (Node node : stack) {
            upper = Math.max(upper, node.upper);
            if (node.upper > best) ++open_nodes;
        }
        return new Result(upper == best ? "OPTIMAL" : "NODE_LIMIT", best_mask, best, upper,
                history.size(), calls, open_nodes, cover, history);
    }
    static void show(String label, Result r, int n) {
        System.out.println(label);
        for (State s : r.history) {
            String lp = s.has_lp ? s.lp_num + "/" + s.lp_den : "NONE";
            System.out.println("step=" + s.iteration + " node=" + s.node_id + " LP=" + lp
                    + " cut=" + (s.cut_upper >= 0 ? Integer.toString(s.cut_upper) : "OFF")
                    + " U=" + (s.upper >= 0 ? Integer.toString(s.upper) : "NONE")
                    + " L=" + s.best_value + " action=" + s.action
                    + " branch=" + (s.branch >= 0 ? Integer.toString(s.branch + 1) : "-"));
        }
        StringBuilder x = new StringBuilder();
        for (int i = 0; i < n; ++i) { if (i != 0) x.append(','); x.append((r.best_mask >> i) & 1); }
        System.out.println(r.status + " x=[" + x + "] value=" + r.value + " upper=" + r.upper
                + " nodes=" + r.processed + " LPs=" + r.bound_calls + " open=" + r.open_nodes);
    }
    public static void main(String[] args) {
        int[] weights = {2, 2}, profits = {3, 3};
        show("branch-and-bound", solve(weights, profits, 3, false, 100), 2);
        show("cover-strengthened", solve(weights, profits, 3, true, 100), 2);
        show("node-limit", solve(weights, profits, 3, false, 1), 2);
    }
}

Expected standard output, identical in all three languages:

• branch-and-bound
• step=1 node=0 LP=9/2 cut=OFF U=4 L=3 action=BRANCH branch=2
• step=2 node=1 LP=9/2 cut=OFF U=4 L=3 action=BRANCH branch=1
• step=3 node=3 LP=NONE cut=OFF U=NONE L=3 action=INFEASIBLE branch=-
• step=4 node=4 LP=3/1 cut=OFF U=3 L=3 action=INTEGRAL branch=-
• step=5 node=2 LP=3/1 cut=OFF U=3 L=3 action=INTEGRAL branch=-
• OPTIMAL x=[1,0] value=3 upper=3 nodes=5 LPs=4 open=0
• cover-strengthened
• step=1 node=0 LP=9/2 cut=3 U=3 L=3 action=BOUND branch=-
• OPTIMAL x=[1,0] value=3 upper=3 nodes=1 LPs=1 open=0
• node-limit
• step=1 node=0 LP=9/2 cut=OFF U=4 L=3 action=BRANCH branch=2
• NODE_LIMIT x=[1,0] value=3 upper=4 nodes=1 LPs=1 open=2

Complexity, Correctness, and Invariants

Let $P$ be the number of processed nodes, $B$ the node budget, and $n$ the number of items. Initial density and cover ordering cost $O(n\log(n+1))$. A processed node scans the ordered items in $O(n)$ time unless a cached bound or infeasibility test prunes it earlier. With the cover enabled, sorting the free cover profits costs up to $O(n\log(n+1))$ per evaluated node; the implementation chooses clarity over precomputing this order.

Thus total work is $O(n\log(n+1)+Pn)$ without the cover and $O((P+1)n\log(n+1))$ with it. With positive-size input and at least one processed node, the best case is an integral or bound-closed root after the initial sort. A zero budget does only initialization. There is no distribution-free average-case polynomial guarantee: tree size depends on the model, bounds, incumbent, and branching order.

Each branch fixes one previously free binary variable. Tree depth is at most $n$, and the full binary tree contains at most $2^{n+1}-1$ nodes. Therefore $$ P\le\min\{B,2^{n+1}-1\}. $$ The no-cut worst-case bound is $O(n2^n+n\log(n+1))$ when the budget permits the entire tree; the cover version has worst-case bound $O(n\log(n+1)2^n)$. These are upper bounds, not a claim that every input reaches the full tree. General MILP also incurs the work of repeated LP solves, separation, and numerical linear algebra, which this specialized single-row bound avoids.

Depth-first search stores at most one deferred sibling per level, so its frontier uses $O(n)$ nodes. Ordering and temporary cover arrays use $O(n)$ space. The returned history retains one constant-size event per processed node, making the actual program's auxiliary storage $O(n+P)$; streaming or omitting history would reduce it to $O(n)$. These counts use bounded-width arithmetic on the documented domain. Exact arithmetic on unrestricted coefficients additionally costs time and memory proportional to intermediate bit lengths.

Why the fractional bound is exact. For the single-capacity relaxation, consider two free items with densities $p_i/w_i\ge p_j/w_j$. If a solution uses positive weight of item $j$ while item $i$ can accept more, transferring a small equal amount of weight from $j$ to $i$ never decreases profit. Repeating gives a density-ordered optimum: full items, at most one fractional item, then zeros. Fixed choices contribute a constant profit and reduce available capacity. Zero-profit free items can be omitted without changing the optimum. The implemented whole-prefix candidate is a subset of this relaxation's full items, so its total weight never exceeds capacity.

Why the search is correct. Use the following four claims together.

1. Feasible incumbent. Initially the empty solution is feasible. Updates come only from fixed choices passing the capacity check plus fully fitted free items. Thus $L$ is always the value of a real feasible integer solution and never decreases.
2. Valid node bounds. The node's LP is a relaxation. Integer objective values justify flooring it. The cover-only problem is another relaxation because every capacity-feasible binary completion satisfies the cover. The minimum of their upper bounds is still an upper bound. A child inherits a valid bound because its feasible set is contained in its parent's.
3. Complete partition. Branching on a free binary variable separates its completions into include and exclude cases, with no overlap or omitted integer point. Infeasible nodes contain no feasible completion. Nodes bounded by $L$ cannot contain a strict improvement. An integral LP optimum already solves its node.
4. Global certificate and termination. Every unresolved improvement belongs to a pending node, so the maximum of cached pending bounds and $L$ bounds the full optimum. Depth grows by one fixed variable per branch and is finite. If this maximum equals $L$, optimality follows; if the budget ends earlier with a larger maximum, return the remaining interval instead.

A subtle distinction matters: finding a solution of value $3$ and proving no solution exceeds $3$ are different events. At the sample root without the cover, only the first has occurred. Either completing the tree or tightening the bound supplies the proof.

Variants, Pitfalls, and Optimizations

Branch-and-bound versus cutting planes versus branch-and-cut. Pure branch-and-bound improves certainty by partitioning the feasible integer choices. A cutting-plane procedure repeatedly tightens a relaxation, without necessarily branching; simply adding arbitrary valid cuts does not guarantee fast convergence or even finite termination for an unspecified procedure. Branch-and-cut uses selected cuts at the root or other nodes and branches when fractional uncertainty remains. General-purpose solvers add presolve, primal heuristics, propagation, node selection, and sophisticated branching to this framework. The Gurobi introduction to mixed-integer programming describes these core mechanisms, and SCIP's cutting-plane slides develop cover and other cut families.

Separate bounds can be weaker than a joint cut LP. Use weights $(2,2,2)$, profits $(4,4,1)$, and capacity $3$. The chosen heaviest-prefix cover is $\mathcal C=\{1,2\}$, giving $x_1+x_2\le1$. The capacity-only LP optimum is $6$, attained at $(1,1/2,0)$. The cover-only optimum is $5$, attained by taking item $3$ and one cover item. The implementation combines these into upper bound $\min(6,5)=5$.

The LP with both constraints has optimum $9/2$, attained at $(1,0,1/2)$. To verify it, let $s=x_1+x_2$ and $t=x_3$. Then $s\le1$, $s+t\le3/2$, $t\le1$, and the objective is $4s+t$. Since $4s+t=3s+(s+t)\le3+3/2=9/2$, that point is optimal. Flooring the joint LP would give integer upper bound $4$, matching the true binary optimum; the implemented separate-bound value $5$ does not prove optimality at the root. Each relaxation excludes a different maximizer, so intersecting their constraints helps beyond taking the smaller separate value.

Other cut families. The same two-parcel inequality can also be obtained by dividing $2x_1+2x_2\le3$ by two and observing that the integer quantity $x_1+x_2$ is at most $\lfloor3/2\rfloor=1$. This is a simple integer-rounding argument. Gomory, mixed-integer rounding, clique, and lifted cover cuts extend the range of useful inequalities; deriving them requires their specific validity conditions. An arbitrary rounding of individual row coefficients is not a substitute for such a proof.

Node policy and heuristics. Include-first depth-first search keeps the frontier small and may find useful incumbents early. Best-bound search processes a pending node with the largest upper bound in a maximization problem and can improve the global certificate more directly, but may retain many nodes. Strong branching tests candidate branches using temporary relaxations; pseudocosts estimate their benefit from prior observations. For this teaching solver, better feasible completions, preprocessing overweight items, or ordering free cover profits once can help. None changes the exponential worst-case bound.

Cut scope and model semantics. A local inequality derived using $x_j=1$ cannot automatically be imposed at the root. A globally valid inequality must preserve every original integer feasible point. A user cut strengthens an already valid relaxation; a constraint needed to define feasibility must actually be enforced whenever accepting an incumbent, including when such constraints are generated lazily. Never use a heuristic candidate before checking all the original model constraints.

Numerical and modeling mistakes. Rounding an LP point can violate capacity, equalities, or linking constraints. Even feasible rounding is only a candidate. With floating-point LP solvers, integrality and feasibility tolerances need consistent interpretation; the exact integer arithmetic here avoids that issue only for its limited model. Overly large big-$M$ constants often weaken relaxations and impair conditioning; derive valid tight bounds or use supported indicator constraints. Avoid discarding symmetric choices unless the symmetry argument preserves at least one representative of every relevant solution.

Edge cases and status claims. Zero profits leave the empty incumbent optimal; the cached-bound check can close the root without an LP. Zero capacity excludes every positive-weight item. An overweight single item forms a singleton cover $x_i\le0$. Empty input is a valid zero-profit problem. On arbitrary MILPs, an infeasible LP proves integer infeasibility, but LP feasibility does not prove integer feasibility. Likewise an unbounded LP relaxation need not mean an unbounded integer model: a constraint $2x=1$ with integer $x$, combined with an unconstrained improving continuous direction, has an unbounded relaxation yet no integer feasible solution. Such cases lie outside the implemented binary family.

If only a capacity-indexed knapsack optimum is required and $C$ is moderate, dynamic programming may be simpler. If the model has several resource constraints, assignment rules, general integer domains, or continuous variables, use an established MILP solver rather than applying this single-row fractional bound as if it solved the full LP.

Practice Problems and Real-World Use

Begin by modifying the sample, then compare the solver's certificate with exhaustive enumeration on small models. For $n$ small enough, enumerate all $2^n$ masks and independently verify capacity and profit. Check not just the final objective but the incumbent's feasibility, every node bound, the include/exclude partition, and the interval returned when a budget stops the run.

An independent oracle for the fractional-knapsack node bound uses its one-variable dual. For fixed-included profit $V$, remaining capacity $R\ge0$, and free set $F$, $$ U_{\mathrm{LP}} =V+\min_{\alpha\ge0}\left(R\alpha+ \sum_{i\in F}\max(0,p_i-\alpha w_i)\right). $$ This convex piecewise-linear function attains a minimum at $\alpha=0$ or a density breakpoint $\alpha=p_i/w_i$; when $F$ is empty, use $\alpha=0$. Evaluating these rational candidates checks the greedy bound without repeating its ordering algorithm.

The accompanying programs were compared on $5207$ shared inputs, including $10$ invalid-domain inputs. The valid set includes exhaustive models of up to three items over weights $\{1,2\}$ and profits $\{0,1,3\}$, randomized models, zero budgets, tied densities, zero profits, and $16$-item boundary cases. Independent checks validated $7449$ LP bounds using the dual formula, checked node bounds against feasible completions, and verified both completed and stopped-search certificates. C++ and Java matched every Python result and recorded event exactly; C++ was also checked with address and undefined-behavior sanitizers.

For a strict independent-bound exercise, find a model where the joint capacity-plus-cover LP optimum is below both separate relaxation optima. State which maximizer each constraint excludes, and distinguish that continuous comparison from flooring an integer-valued objective bound. For real planning models, explicitly write every feasibility condition, retain a feasible incumbent, and report the remaining gap if the solver stops early.