Mauro Piacentini

An Exact Algorithm for Quadratic Integer Minimization using Ellipsoidal Relaxations

  • Christoph Buchheim
  • Marianna De Santis
  • Laura Palagi
  • Mauro Piacentini
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Quadratic Programming Tags ,

    We propose a branch-and-bound algorithm for minimizing a not necessarily convex quadratic function over integer variables. The algorithm is based on lower bounds computed as continuous minima of the objective function over appropriate ellipsoids. In the nonconvex case, we use ellipsoids enclosing the feasible region of the problem. In spite of the nonconvexity, these minima … Read more

    SpeeDP: A new algorithm to compute the SDP relaxations of Max-Cut for very large graphs

  • Luigi Grippo
  • Veronica Piccialli
  • Laura Palagi
  • Mauro Piacentini
  • Giovanni Rinaldi
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , , , ,

    We consider low-rank semidefinite programming (LRSDP) relaxations of unconstrained {-1,1} quadratic problems (or, equivalently, of Max-Cut problems) that can be formulated as the nonconvex nonlinear programming problem of minimizing a quadratic function subject to separable quadratic equality constraints. We prove the equivalence of the LRSDP problem with the unconstrained minimization of a new merit function … Read more