Skip to main content
SpringerLink
Log in

A branch-and-cut algorithm based on semidefinite programming for the minimum k-partition problem

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

The minimum k-partition (MkP) problem is the problem of partitioning the set of vertices of a graph into k disjoint subsets so as to minimize the total weight of the edges joining vertices in the same partition. The main contribution of this paper is the design and implementation of a branch-and-cut algorithm based on semidefinite programming (SBC) for the MkP problem. The two key ingredients for this algorithm are: the combination of semidefinite programming with polyhedral results; and a novel iterative clustering heuristic (ICH) that finds feasible solutions for the MkP problem. We compare ICH to the hyperplane rounding techniques of Goemans and Williamson and of Frieze and Jerrum, and the computational results support the conclusion that ICH consistently provides better feasible solutions for the MkP problem. ICH is used in our SBC algorithm to provide feasible solutions at each node of the branch-and-bound tree. The SBC algorithm computes globally optimal solutions for dense graphs with up to 60 vertices, for grid graphs with up to 100 vertices, and for different values of k, providing a fast exact approach for k≥3.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Barahona, F., & Mahjoub, A. (1986). On the cut polytope. Mathematical Programming, 36, 157–173.

    Article  Google Scholar 

  • Barahona, F., Grötschel, M., Jünger, M., & Reinelt, G. (1988). An application of combinatorial optimization to statistical physics and circuit layout design. Operations Research, 36, 493–513.

    Article  Google Scholar 

  • Biq Mac solver. (2007). http://biqmac.uni-klu.ac.at/.

  • Borchers, B. (1999). CSDP, a C library for semidefinite programming. Optimization Methods and Software, 11/12(1–4), 613–623.

    Article  Google Scholar 

  • Boros, E., & Hammer, P. (1991). The max-cut problem and quadratic 0–1 optimization: Polyhedral aspects, relaxations and bounds. Annals of Operations Research, 33, 151–180.

    Article  Google Scholar 

  • Chopra, S., & Rao, M. R. (1993). The partition problem. Mathematical Programming, 59, 87–115.

    Article  Google Scholar 

  • Chopra, S., & Rao, M. R. (1995). Facets of the k-partition problem. Discrete Applied Mathematics, 61, 27–48.

    Article  Google Scholar 

  • de Klerk, E., Pasechnik, D., & Warners, J. (2004). Approximate graph colouring and max-k-cut algorithms based on the theta function. Journal of Combinatorial Optimization, 8(3), 267–294.

    Article  Google Scholar 

  • Deza, M., & Laurent, M. (1997). Algorithms and combinatorics. Geometry of cuts and metrics. Berlin: Springer.

    Google Scholar 

  • Deza, M., Grötschel, M., & Laurent, M. (1991). Complete descriptions of small multicut polytopes. Applied Geometry and Discrete Mathematics—The Victor Klee Festschrift, 4, 205–220.

    Google Scholar 

  • Domingo-Ferrer, J., & Mateo-Sanz, J. M. (2002). Practical data-oriented microaggregation for statistical disclosure control. IEEE Transactions on Knowledge and Data Engineering, 14(1), 189–201.

    Article  Google Scholar 

  • Eisenblätter, A. (2002). The semidefinite relaxation of the k-partition polytope is strong. In Proceedings of the 9th international IPCO conference on integer programming and combinatorial optimization (Vol. 2337, pp. 273–290).

  • Elf, M., Jünger, M., & Rinaldi, G. (2003). Minimizing breaks by maximizing cuts. Operations Research Letters, 31(5), 343–349.

    Article  Google Scholar 

  • Frieze, A., & Jerrum, M. (1997). Improved approximation algorithms for max k-cut and max bisection. Algorithmica, 18, 67–81.

    Article  Google Scholar 

  • Ghaddar, B. (2007). A branch-and-cut algorithm based on semidefinite programming for the minimum k -partition problem. Master’s thesis, University of Waterloo

  • Goemans, M., & Williamson, D. (1994). New ¾-approximation algorithms for the maximum satisfiability problem. SIAM Journal of Discrete Mathematics, 7(4), 656–666.

    Article  Google Scholar 

  • Helmberg, C., & Rendl, F. (1998). Solving quadratic (0, 1)-problems by semidefinite programs and cutting planes. Mathematical Programming, Series A, 82(3), 291–315.

    Article  Google Scholar 

  • Kaibel, V., Peinhardt, M., & Pfetsch, M. E. (2007). Orbitopal fixing. In M. Fischetti & D. P. Williamson (Eds.), Lecture notes in computer science : Vol. 4513. IPCO (pp. 74–88). Berlin: Springer.

    Google Scholar 

  • Lee, L. W., Katzgraber, H. G., & Young, A. P. (2006). Critical behavior of the three- and ten-state short-range Potts glass: A Monte Carlo study. Physical Review B, 74, 104–116.

    Google Scholar 

  • Liers, F., Jünger, M., Reinelt, G., & Rinaldi, G. (2004). Computing exact ground states of hard ising spin glass problems by branch-and-cut. In New optimization algorithms in physics (pp. 47–68). New York: Wiley.

    Chapter  Google Scholar 

  • Lisser, A., & Rendl, F. (2003). Telecommunication clustering using linear and semidefinite programming. Mathematical Programming, 95, 91–101.

    Article  Google Scholar 

  • Lovász, L. (1979). On the Shannon capacity of a graph. IEEE Transactions Information Theory, IT-25, 1–7.

    Article  Google Scholar 

  • Mitchell, J. (2001). Branch-and-cut for the k -way equipartition problem (Technical report). Department of Mathematical Sciences, Rensselaer Polytechnic Institute.

  • Mitchell, J. E. (2003). Realignment in the National Football League: Did they do it right? Naval Research Logistics, 50(7), 683–701.

    Article  Google Scholar 

  • Rendl, F., Rinaldi, G., & Wiegele, A. (2007). A branch and bound algorithm for max-cut based on combining semidefinite and polyhedral relaxations. Integer Programming and Combinatorial Optimization, 4513, 295–309.

    Article  Google Scholar 

  • Rinaldi, G. (1996). Rudy. http://www-user.tu-chemnitz.de/~helmberg/rudy.tar.gz.

  • Spin-glass server. (1996). http://www.informatik.uni-koeln.de/ls_juenger/research/sgs/index.html.

  • Wiegele, A. (2006). Nonlinear optimization techniques applied to combinatorial optimization problems. Ph.D. thesis, Alpen-Adria-Universität Klagenfurt.

Download references

Author information

Authors and Affiliations

  1. Department of Management Sciences, University of Waterloo, 200 University Avenue West, Waterloo, Ontario, Canada, N2L 3G1

    Bissan Ghaddar & Miguel F. Anjos

  2. Institut für Informatik, Universität zu Köln, Pohligstr. 1, 50969, Köln, Germany

    Frauke Liers

Authors
  1. Bissan Ghaddar
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Miguel F. Anjos
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Frauke Liers
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Miguel F. Anjos.

Additional information

Dedicated to the memory of Peter L. Hammer and in celebration of his outstanding contribution to the field of operations research.

Partially supported by the Marie Curie RTN 504438 (ADONET) funded by the European Commission. BG and MFA were supported by NSERC Discovery Grant 312125 and MITACS Network of Centres of Excellence and Canada Foundation for Innovation. FL was supported by the German Science Foundation under contract Li 1675/1.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ghaddar, B., Anjos, M.F. & Liers, F. A branch-and-cut algorithm based on semidefinite programming for the minimum k-partition problem. Ann Oper Res 188, 155–174 (2011). https://doi.org/10.1007/s10479-008-0481-4

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-008-0481-4

Keywords

Search

Navigation