Integer programming

An integer program optimizes an objective under constraints with some or all variables restricted to integers. Its continuous relaxation removes those integrality restrictions; a relaxed optimum bounds the integer optimum in the appropriate direction.

Partition positive item weights into two bins to minimize the heavier total. The optimum is at least both half the total weight and the largest individual weight. This is two-machine makespan minimization, rather than the version of bin packing that minimizes the number of fixed-capacity bins.

For integer weights, subset-sum dynamic programming finds the greatest achievable total at most $s/2$ in time $O(ns)$, where $s$ is the total weight. For rational weights and $0<\epsilon <1$, scale by $K=\epsilon s/(2n)$ and round down to $q_i=\lfloor w_i/K\rfloor$. The scaled total is at most $2n/\epsilon$, so exact dynamic programming costs $O(n^2/\epsilon )$ arithmetic operations. Lifting its partition to the original weights increases the maximum load by at most $nK\le \epsilon \mathrm{OPT}$. Thus it is a fully polynomial-time approximation scheme for this two-bin problem. Bit complexity also accounts for the rational input and epsilon encodings.

Put each successive item into a currently lighter bin. Before receiving weight $w_j$, that bin contains at most half the total weight already assigned, hence at most $(s-w_j)/2$, where $s$ is the overall total. Apply this to the last item in a finally heaviest bin to get $\mathrm{ALG}\le s/2+w_{\max }/2$. Since $\mathrm{OPT}\ge \max (s/2,w_{\max })$, the approximation ratio is at most $3/2$. Ordered weights $1,1,2$ give loads $3,1$ rather than the optimal $2,2$, proving the bound is sharp. Its relative-error guarantee is $\epsilon =1/2$.

If $Bz=b$, $z\ge 0$ has an integer solution, with $N$ variables and all data bounded by $M\ge 1$, it has one satisfying the displayed bound. Apply support-minimal rays of a nonnegative kernel to $(z,1)$ in the cone $\{(u,t)\ge 0:Bu=bt\}$. Its integer generators have coordinates bounded by $D=(N+1)!M^{N+1}$. Generators with positive last coordinate normalize to feasible points with coordinates at most $D$; their coefficients form a convex combination. The remaining generators are integer recession directions. Subtract the integer parts of their coefficients from the original integer solution. The result remains integral and feasible and has coordinates at most $D+(N+1)D$. Its binary length is polynomial in the input size. Splitting unrestricted integer variables and adding integer slacks reduces general integer linear feasibility to this form, proving its membership in NP.

Given bidders' values $v_i(S)$ for item bundles, the winner determination problem maximizes ${\sum }_i{v}_i(S_i)$ over disjoint allocated bundles. When every item must be assigned, the bundles form a partition. General values permit complements and difficult combinatorial search; monotone submodular set functions permit a greedy half-approximation. Complexity claims must specify whether the values are supplied explicitly or by a value oracle.

Allocate each remaining item to a bidder with greatest current marginal gain. For nonnegative monotone submodular set functions, this uses $O(m{n}^2)$ value queries and achieves the displayed guarantee. To prove it by induction, let the first allocation give item $j$ to bidder $r$, and set $w=v_r(\{j\})$. Contract that item into bidder $r$'s value by replacing it with $v_r^{\prime }(S)=v_r(S\cup \{j\})-w$ and leave the other bidders' values unchanged. The remaining greedy run is identical, and $A(v)=w+A(v^{\prime })$. Move $j$ from its owner in an optimal allocation to $r$. Submodularity bounds the owner's loss by its initial singleton marginal, which is no larger than the selected greedy marginal and hence no larger than $w$. The receiver's value cannot decrease, so $\mathrm{Opt}(v^{\prime })\ge \mathrm{Opt}(v)-2w$. Induction proves the guarantee, with the zero-item case immediate even for nonzero empty-bundle values.

A permutation assigns facilities to locations, and the objective combines their pairwise interactions with pairwise location costs. Ordered-pair and unordered-pair conventions differ by a factor of two for symmetric data. The decision version is NP-complete: letting $A$ record a directed cycle makes the objective exactly the length of a travelling salesman problem tour under the ordering given by the permutation. The optimization version is NP-hard.

For each facility $i$ and location $k$, independently minimize its row contribution over bijections from the other facilities to the other locations, giving ${\ell }_{ik}$. Every complete assignment has row contribution at least its corresponding ${\ell }_{ik}$, so minimizing their sum is a lower bound on the quadratic objective. Fixed assignments are retained as constraints in this assignment problem, which the Hungarian algorithm solves. The independently optimal rows need not be simultaneously realizable, explaining why the bound can be strict.

A branch-and-bound search partitions a feasible set, maintains a feasible incumbent, and prunes subproblems using bounds that cannot improve that incumbent. For a quadratic knapsack problem, fixing a selected set $S$ adds its exact quadratic value as a constant and replaces remaining profits by $v_i+2{\sum }_{j\in S}{p}_{ij}$ under the ordered-pair convention. Residual fractional row bounds for quadratic knapsack and a Lagrangian knapsack bound can then be recomputed. Worst-case search remains exponential.

An incumbent solution is the best feasible solution found so far by an optimization search. Its objective value is an upper bound on a minimization optimum and a lower bound on a maximization optimum; bounds on unexplored subproblems can be compared with it to prune the search.

// Target: combinatorics.bigb

For minimization, best-bound search expands the active branch and bound node with smallest lower bound. A feasible completed assignment supplies an incumbent upper bound. Nodes with lower bound at least that incumbent can be discarded when only one optimum is needed. Search ends with an optimality certificate when no active node can improve the incumbent.

// Target: combinatorics.bigb

The knapsack problem selects items of prescribed weights and profits under a total-weight capacity. The 0-1 knapsack problem permits each item at most once; bounded and unbounded multiplicity variants use different integer restrictions. Nonnegative weights and capacity are assumed here.

The quadratic knapsack problem includes pairwise interactions between selected items. For symmetric $p_{ij}$, a sum over all ordered pairs counts each unordered interaction twice; an alternative convention sums only over $i<j$. The objective convention must be kept consistent when bounding or fixing variables.

Conditioning on selecting item $i$ leaves capacity $B-w_i$. Its fractional knapsack problem bounds that item's total interaction with the other selected items. Thus the ordered-pair quadratic objective is at most ${\sum }_i(v_i+q_i)x_i$. Remove overweight items before defining their residual-capacity problems.

This linear programming relaxation allows a fraction of each item. With positive weights, sort decreasing profit-to-weight ratios and fill capacity in that order, using at most one fractional item. An exchange argument proves optimality. Negative-profit items are omitted and positive-profit zero-weight items are included for free.

This binary integer program selects each item at most once. Exact optimization is NP-hard; the fractional knapsack problem gives an upper bound and supports a half-approximation algorithm for knapsack.

After removing overweight items and handling free items, compare the feasible density-sorted prefix with the best feasible singleton. The fractional knapsack problem optimum is at most the sum of their profits, so the better solution has approximation ratio $1/2$.

A cutting-plane method repeatedly adds valid inequalities that exclude a current relaxed solution while preserving all feasible integer solutions. Gomory fractional cuts provide such inequalities from a fractional simplex dictionary.

For an all-integer dictionary row $x_B+{\sum }_j{a}_j{x}_j=b$ with nonnegative variables, this cut follows because $x_B+{\sum }_j\lfloor a_j\rfloor x_j$ is an integer and ${\sum }_j\{a_j\}{x}_j\ge 0$. Consequently that integer is at most $\lfloor b\rfloor$. Negative coefficients use the usual fractional part $u-\lfloor u\rfloor$, so $\{-1/5\}=4/5$. Normalize a resulting inequality sensibly before introducing a new integer-valued slack variable.

For a nonnegative all-integer row $x_B+{\sum }_j{a}_j{x}_j=b$ with $a_j>0$, the Gomory fractional cut requires ${\sum }_j\{a_j\}{x}_j\ge \{b\}$. The original row gives ${\sum }_j{a}_j{x}_j\le b$. If a constant $\kappa$ satisfies $\{a_j\}\le \kappa a_j$ for every $j$ and $\kappa b<\{b\}$, these inequalities contradict the cut. A single row therefore certifies integer infeasibility. Slacks may be used as integer variables when the original constraint coefficients and right sides are integral and the decision variables are integral.