Maribel Montenegro

SDP-based Branch-and-Bound for Non-convex Quadratic Integer Optimization

  • Christoph Buchheim
  • Maribel Montenegro
  • Angelika Wiegele
    • Categories Quadratic Programming, Semi-definite Programming Tags , ,

    Semidefinite programming (SDP) relaxations have been intensively used for solving discrete quadratic optimization problems, in particular in the binary case. For the general non-convex integer case with box constraints, the branch-and-bound algorithm Q-MIST has been proposed [11], which is based on an extension of the well-known SDP-relaxation for max-cut. For solving the resulting SDPs, Q-MIST … Read more

    A coordinate ascent method for solving semidefinite relaxations of non-convex quadratic integer programs

  • Christoph Buchheim
  • Maribel Montenegro
  • Angelika Wiegele
    • Categories Integer Programming, Semi-definite Programming Tags , ,

    We present a coordinate ascent method for a class of semidefinite programming problems that arise in non-convex quadratic integer optimization. These semidefinite programs are characterized by a small total number of active constraints and by low-rank constraint matrices. We exploit this special structure by solving the dual problem, using a barrier method in combination with … Read more