Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Martin Grötschel—The Early Years in Bonn and Augsburg Read chapter Read first chapter

2013 | OriginalPaper | Chapter

Solving k-Way Graph Partitioning Problems to Optimality: The Impact of Semidefinite Relaxations and the Bundle Method

Authors : Miguel F. Anjos, Bissan Ghaddar, Lena Hupp, Frauke Liers, Angelika Wiegele

Published in: Facets of Combinatorial Optimization

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This paper is concerned with computing global optimal solutions for maximum k-cut problems. We improve on the SBC algorithm of Ghaddar, Anjos and Liers in order to compute such solutions in less time. We extend the design principles of the successful BiqMac solver for maximum 2-cut to the general maximum k-cut problem. As part of this extension, we investigate different ways of choosing variables for branching. We also study the impact of the separation of clique inequalities within this new framework and observe that it frequently reduces the number of subproblems considerably. Our computational results suggest that the proposed approach achieves a drastic speedup in comparison to SBC, especially when k=3. We also made a comparison with the orbitopal fixing approach of Kaibel, Peinhardt and Pfetsch. The results suggest that, while their performance is better for sparse instances and larger values of k, our proposed approach is superior for smaller k and for dense instances of medium size. Furthermore, we used CPLEX for solving the ILP formulation underlying the orbitopal fixing algorithm and conclude that especially on dense instances the new algorithm outperforms CPLEX by far.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter A New Algorithm for MINLP Applied to Gas Transport Energy Cost Minimization
next chapter On Perspective Functions and Vanishing Constraints in Mixed-Integer Nonlinear Optimal Control
Literature
1.
Anjos, M.F., Wolkowicz, H.: Geometry of semidefinite max-cut relaxations via matrix ranks. J. Comb. Optim. 6(3), 237–270 (2002) MathSciNetMATHCrossRef
2.
Anjos, M.F., Wolkowicz, H.: Strengthened semidefinite relaxations via a second lifting for the max-cut problem. Discrete Appl. Math. 119(1–2), 79–106 (2002) MathSciNetMATHCrossRef
3.
Anjos, M.F., Liers, F., Pardella, G., Schmutzer, A.: Engineering branch-and-cut algorithms for the equicut problem. Cahier du GERAD G-2012-15, GERAD, Montreal, QC, Canada (2012). In: Fields Institute Communications on Discrete Geometry and Optimization. Springer, Berlin (2013, to appear)
4.
Armbruster, M., Fügenschuh, M., Helmberg, C., Martin, A.L.: LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison. Math. Program. Comput. 4(3), 275–306 (2012) MathSciNetCrossRef
5.
6.
Barahona, F., Grötschel, M., Jünger, M., Reinelt, G.: An application of combinatorial optimization to statistical physics and circuit layout design. Oper. Res. 36, 493–513 (1988) MATHCrossRef
7.
8.
Borchers, B.: CSDP, a C library for semidefinite programming. Optim. Methods Softw. 11/12(1–4), 613–623 (1999) MathSciNetCrossRef
9.
Boros, E., Hammer, P.: The max-cut problem and quadratic 0–1 optimization: polyhedral aspects, relaxations and bounds. Ann. Oper. Res. 33, 151–180 (1991) MathSciNetMATHCrossRef
10.
Brunetta, L., Conforti, M., Rinaldi, G.: A branch-and-cut algorithm for the equicut problem. Math. Program., Ser. B 78(2), 243–263 (1997) MathSciNetMATHCrossRef
11.
12.
13.
14.
de Klerk, E., Pasechnik, D., Warners, J.: On approximate graph colouring and max-k-cut algorithms based on the ϑ-function. J. Comb. Optim. 8(3), 267–294 (2004) MathSciNetMATHCrossRef
15.
Deza, M., Laurent, M.: Geometry of Cuts and Metrics. Algorithms and Combinatorics. Springer, Berlin (1997) MATH
16.
Deza, M., Grötschel, M., Laurent, M.: Complete descriptions of small multicut polytopes. In: Applied Geometry and Discrete Mathematics—The Victor Klee Festschrift, pp. 205–220, Am. Math. Soc., Providence (1991)
17.
Dolan, E., Moré, J.: Benchmarking optimization software with performance profiles. Math. Program., Ser. A, 91(2), 201–213 (2002) MATHCrossRef
18.
Eisenblätter, A.: The semidefinite relaxation of the k-partition polytope is strong. In: Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol. 2337, pp. 273–290. Springer, Berlin (2002) CrossRef
19.
20.
Fischer, I., Gruber, G., Rendl, F., Sotirov, R.: Computational experience with a bundle approach for semidefinite cutting plane relaxations of max-cut and equipartition. Math. Program., Ser. B 105(2–3), 451–469 (2006) MathSciNetMATHCrossRef
21.
22.
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(1), 155–174 (2011) MathSciNetMATHCrossRef
23.
Goemans, M., Williamson, D.: New \(\frac{3}{4}\)-approximation algorithms for the maximum satisfiability problem. SIAM J. Discrete Math. 7(4), 656–666 (1994) MathSciNetMATHCrossRef
24.
Helmberg, C.: A cutting plane algorithm for large scale semidefinite relaxations. In: The Sharpest Cut. MPS/SIAM Ser. Optim., pp. 233–256. SIAM, Philadelphia (2004)
25.
26.
Helmberg, C., Rendl, F.: Solving quadratic (0,1)-problems by semidefinite programs and cutting planes. Math. Program., Ser. A 82(3), 291–315 (1998) MathSciNetMATHCrossRef
27.
Helmberg, C., Rendl, F.: A spectral bundle method for semidefinite programming. SIAM J. Optim. 10(3), 673–696 (2000) (electronic) MathSciNetMATHCrossRef
28.
Helmberg, C., Rendl, F., Vanderbei, R.J., Wolkowicz, H.: An interior-point method for semidefinite programming. SIAM J. Optim. 6(2), 342–361 (1996) MathSciNetMATHCrossRef
29.
Kaibel, V., Peinhardt, M., Pfetsch, M.: Orbitopal fixing. In: Fischetti, M., Williamson, D. (eds.) Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol. 4513, pp. 74–88. Springer, Berlin (2007) CrossRef
30.
31.
Kiwiel, K.C.: Methods of Descent for Nondifferentiable Optimization. Lecture Notes in Mathematics, vol. 1133. Springer, Berlin (1985) MATH
32.
Laurent, M.: Semidefinite relaxations for max-cut. In: The Sharpest Cut. MPS/SIAM Ser. Optim., pp. 257–290. SIAM, Philadelphia (2004)
33.
Laurent, M., Poljak, S.: On a positive semidefinite relaxation of the cut polytope. Linear Algebra Appl. 223/224, 439–461 (1995) MathSciNetCrossRef
34.
Laurent, M., Poljak, S.: On the facial structure of the set of correlation matrices. SIAM J. Matrix Anal. Appl. 17(3), 530–547 (1996) MathSciNetMATHCrossRef
35.
Lemaréchal, C.: Bundle methods in nonsmooth optimization. In: Nonsmooth Optimization, Proc. IIASA Workshop, Laxenburg, 1977. IIASA Proc. Ser., vol. 3, pp. 79–102. Pergamon, Oxford (1978)
36.
Lemaréchal, C., Nemirovskii, A., Nesterov, Y.: New variants of bundle methods. Math. Program., Ser. B 69(1), 111–147 (1995) MATHCrossRef
37.
Liers, F., Jünger, M., Reinelt, G., Rinaldi, G.: Computing exact ground states of hard Ising spin glass problems by branch-and-cut. In: New Optimization Algorithms in Physics, pp. 47–68. Wiley, New York (2004)
38.
Liers, F., Lukic, J., Marinari, E., Pelissetto, A., Vicari, E.: Zero-temperature behavior of the random-anisotropy model in the strong-anisotropy limit. Phys. Rev. B 76(17), 174423 (2007) CrossRef
39.
40.
41.
42.
43.
Mitchell, J.: Branch-and-cut for the k-way equipartition problem. Technical report, Department of Mathematical Sciences, Rensselaer Polytechnic Institute (2001)
44.
Mitchell, J.E.: Realignment in the National Football League: did they do it right? Nav. Res. Logist. 50(7), 683–701 (2003) MATHCrossRef
45.
Palagi, L., Piccialli, V., Rendl, F., Rinaldi, G., Wiegele, A.: Computational approaches to max-cut. In: Handbook on Semidefinite, Conic and Polynomial Optimization. Internat. Ser. Oper. Res. Management Sci., vol. 166, pp. 821–847. Springer, New York (2012) CrossRef
46.
47.
Rendl, F., Rinaldi, G., Wiegele, A.: Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Math. Program. 121, 307–335 (2010) MathSciNetMATHCrossRef
48.
49.
Schramm, H., Zowe, J.: A version of the bundle idea for minimizing a nonsmooth function: conceptual idea, convergence analysis, numerical results. SIAM J. Optim. 2(1), 121–152 (1992) MathSciNetMATHCrossRef
50.
Metadata
Title
Solving k-Way Graph Partitioning Problems to Optimality: The Impact of Semidefinite Relaxations and the Bundle Method
Authors
Miguel F. Anjos
Bissan Ghaddar
Lena Hupp
Frauke Liers
Angelika Wiegele
Copyright Year
2013
Publisher
Springer Berlin Heidelberg
Book
Facets of Combinatorial Optimization

Print ISBN: 978-3-642-38188-1

Electronic ISBN: 978-3-642-38189-8

Copyright Year: 2013

DOI
https://doi.org/10.1007/978-3-642-38189-8_15