An Effective Branch-and-Bound Algorithm for Convex Quadratic Integer Programming

We present a branch-and-bound algorithm for minimizing a convex quadratic objective function over integer variables subject to convex constraints. In a given node of the enumeration tree, corresponding to the fixing of a subset of the variables, a lower bound is given by the continuous minimum of the restricted objective function. We improve this bound … Read more

Lattice-based Algorithms for Number Partitioning in the Hard Phase

The number partitioning problem (NPP) is to divide n numbers a_1,…,a_n into two disjoint subsets such that the difference between the two subset sums – the discrepancy, D, is minimized. In the balanced version of NPP (BalNPP), the subsets must have the same cardinality. With $a_j$s chosen uniformly from $[1,R]$, R > 2^n gives the … Read more