closest vector problem

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

  • Christoph Buchheim
  • Alberto Caprara
  • Andrea Lodi
    • Categories (Mixed) Integer Nonlinear Programming, Convex Optimization, Quadratic Programming Tags ,

    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

  • Bala Krishnamoorthy
  • Nathan Moyer
  • William Webb
    • Categories Approximation Algorithms, Combinatorial Optimization, Integer Programming Tags , , ,

    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