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.

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.

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.