Biq Mac

Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations. We present a method for finding exact solutions of Max-Cut, the problem of finding a cut of maximum weight in a weighted graph. We use a Branch-and-Bound setting that applies a dynamic version of the bundle method as bounding procedure. This approach uses Lagrangian duality to obtain a “nearly optimal” solution of the basic semidefinite Max-Cut relaxation, strengthened by triangle inequalities. The expensive part of our bounding procedure is solving the basic semidefinite relaxation of the Max-Cut problem, which has to be done several times during the bounding process. We review other solution approaches and compare the numerical results with our method. We also extend our experiments to instances of unconstrained quadratic 0-1 optimization and to instances of the graph equipartition problem. The experiments show that our method nearly always outperforms all other approaches. In particular, for dense graphs, where linear programming-based methods fail, our method performs very well. Exact solutions are obtained in a reasonable time for any instance of size up to $n = 100$, independent of the density. For some problems of special structure, we can solve even larger problem classes. We could prove optimality for several problems of the literature where, to the best of our knowledge, no other method is able to do so.


References in zbMATH (referenced in 36 articles , 1 standard article )

Showing results 1 to 20 of 36.
Sorted by year (citations)

1 2 next

  1. Bergman, David; Cire, Andre A.; van Hoeve, Willem-Jan; Hooker, J.N.: Discrete optimization with decision diagrams (2016)
  2. Dong, Hongbo: Relaxing nonconvex quadratic functions by multiple adaptive diagonal perturbations (2016)
  3. Kim, Sunyoung; Kojima, Masakazu; Toh, Kim-Chuan: A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems (2016)
  4. Rendl, F.: Semidefinite relaxations for partitioning, assignment and ordering problems (2016)
  5. van Dam, E.R.; Sotirov, R.: New bounds for the $\max$-$k$-cut and chromatic number of a graph (2016)
  6. Delling, Daniel; Fleischman, Daniel; Goldberg, Andrew V.; Razenshteyn, Ilya; Werneck, Renato F.: An exact combinatorial algorithm for minimum graph bisection (2015)
  7. Goldberg, Noam; Leyffer, Sven: An active-set method for second-order conic-constrained quadratic programming (2015)
  8. Hungerländer, P.: A semidefinite optimization approach to the target visitation problem (2015)
  9. Lieder, Felix; Rad, Fatemeh Bani Asadi; Jarre, Florian: Unifying semidefinite and set-copositive relaxations of binary problems and randomization techniques (2015)
  10. Xia, Yong; Xing, Wenxun: Parametric Lagrangian dual for the binary quadratic programming problem (2015)
  11. Allouche, David; André, Isabelle; Barbe, Sophie; Davies, Jessica; de Givry, Simon; Katsirelos, George; O’Sullivan, Barry; Prestwich, Steve; Schiex, Thomas; Traoré, Seydou: Computational protein design as an optimization problem (2014)
  12. Bonato, Thorsten; Jünger, Michael; Reinelt, Gerhard; Rinaldi, Giovanni: Lifting and separation procedures for the cut polytope (2014)
  13. Burer, Samuel; Kim, Sunyoung; Kojima, Masakazu: Faster, but weaker, relaxations for quadratically constrained quadratic programs (2014)
  14. Krislock, Nathan; Malick, Jér^ome; Roupin, Frédéric: Improved semidefinite bounding procedure for solving max-cut problems to optimality (2014)
  15. Lin, Geng; Zhu, Wenxing: Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem (2014)
  16. Anjos, Miguel F.; Ghaddar, Bissan; Hupp, Lena; Liers, Frauke; Wiegele, Angelika: Solving $k$-way graph partitioning problems to optimality: the impact of semidefinite relaxations and the bundle method (2013)
  17. Anjos, Miguel F.; Liers, Frauke; Pardella, Gregor; Schmutzer, Andreas: Engineering branch-and-cut algorithms for the equicut problem (2013)
  18. Buchheim, Christoph; Wiegele, Angelika: Semidefinite relaxations for non-convex quadratic mixed-integer programming (2013)
  19. Engau, Alexander; Anjos, Miguel F.; Bomze, Immanuel: Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem (2013)
  20. Hager, William W.; Phan, Dzung T.; Zhang, Hongchao: An exact algorithm for graph partitioning (2013)

1 2 next