Skip to main content
SpringerLink
Log in

The max-cut problem and quadratic 0–1 optimization; polyhedral aspects, relaxations and bounds

  • Section III Graph-Theoretical Aspects Of TND
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

Given a graphG, themaximum cut problem consists of finding the subsetS of vertices such that the number of edges having exactly one endpoint inS is as large as possible. In the weighted version of this problem there are given real weights on the edges ofG, and the objective is to maximize the sum of the weights of the edges having exactly one endpoint in the subsetS. In this paper, we consider the maximum cut problem and some related problems, likemaximum-2-satisfiability, weighted signed graph balancing. We describe the relation of these problems to the unconstrained quadratic 0–1 programming problem, and we survey the known methods for lower and upper bounds to this optimization problem. We also give the relation between the related polyhedra, and we describe some of the known and some new classes of facets for them.

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

  1. V.D. Agrawal and S.C. Seth,Test Generation for VLSI Chips (IEEE Computer Society Press, 1988).

  2. N. Alon, The CW-inequalities for vectors inl 1, Eur. J. Combinatorics 10(1990).

  3. W.P. Adams and P.M. Dearing, On the equivalence between roof duality and Lagrangian duality for unconstrained 0–1 quadratic programming problems, Technical Report No. URI-061, The Clemson University (1988).

  4. E. Balas and J.B. Mazzola, Nonlinear 0–1 programming: I. Linearization techniques and II. Dominance relations and algorithms, Math. Progr. 30(1984)1–45.

    Google Scholar 

  5. M. Balinski, On a selection problem, Manag. Sci. 17(1970)230–231.

    Google Scholar 

  6. F. Barahona, The max-cut problem in graphs not contractible toK 5, Oper. Res. Lett. 2(1983)107–111.

    Google Scholar 

  7. F. Barahona, A solvable case of quadratic 0–1 programming, Discr. Appl. Math. 13(1986)23–26.

    Google Scholar 

  8. F. Barahona, On cuts and matchings in planar graphs, Research Report No. 88503-OR, Institut für Operations Research, Universität Bonn (1988).

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

    Google Scholar 

  10. F. Barahona, M. Grötschel and A.R. Mahjoub, Facets of the bipartite subgraph polytope, Math. Oper. Res. 10(1985)340–358.

    Google Scholar 

  11. F. Barahona, M. Jüngert and G. Reinelt, Experiments in quadratic 0–1 programming, Res. Rep. No. 7, Institut für Mathematik, Universität Augsburg (1987).

  12. F. Barahona and A.R. Mahjoub, On the cut polytope, Math. Progr. 36(1986)157–173.

    Google Scholar 

  13. A. Billionnet and B. Jaumard, A decomposition method for minimizing quadratic pseudo-Boolean functions, Oper. Res. Lett. 8(1989)161–163.

    Google Scholar 

  14. S.H. Bokhari,Assignment Problems in Parallel and Distributed Computing (Kluwer Academic, Boston/Dordrecht/Lancaster, 1987).

    Google Scholar 

  15. E. Boros, Y. Crama and P.L. Hammer, Upper bounds for quadratic 0–1 maximization problems, Oper. Res. Lett. 9(1990)73–79.

    Google Scholar 

  16. E. Boros, Y. Crama and P.L. Hammer, Chvátal cuts, and odd cycle inequalities in quadratic 0–1 optimization, SIAM J. Discr. Math., to appear.

  17. E. Boros and P.L. Hammer, On clustering problems with connected optima in Euclidean spaces, Discr. Math. 75(1989)81–88.

    Google Scholar 

  18. E. Boros and P.L. Hammer, A max-flow approach to improved roof-duality in quadratic 0–1 minimization, RUTCOR Research Report 15-89, Rutgers University, New Brunswick, NJ (1989).

    Google Scholar 

  19. E. Boros and P.L. Hammer, Cut-polytopes, Boolean quadric polytopes and nonnegative quadratic pseudo-Boolean functions, Math. Oper. Res., to appear.

  20. E. Boros and P.L. Hammer, On extremal nonnegative quadratic pseudo-Boolean functions, Manuscript (1990).

  21. E. Boros, P.L. Hammer and X. Sun, The DDT method for quadratic 0–1 minimization, RUTCOR Research Report 39-89, Rutgers University, New Brunswick, NJ (1989).

    Google Scholar 

  22. J.-M. Bourjolly, Integral and fractional node-packings, and pseudo-Boolean programs, Ph.D. Dissertation, Waterloo, Ontario (1986).

  23. J.-M. Bourjolly, P.L. Hammer, W.R. Pulleyblank and B. Simeone, Combinatorial methods for bounding a quadratic pseudo-Boolean function, Research Report CORR 89-21, University of Waterloo (1989).

  24. S.T. Chakradhar, M.L. Bushnell and V.D. Agrawal, Automatic test pattern generation using neural networks, in:Proc. Int. Conf. on Computer-Aided Design (IEEE, 1988), pp. 416–419.

  25. C.K. Cheng, S.Z. Yao and T.C. Hu, The orientation of modules based on graph decomposition, IEEE Trans. Comput. C-40(1991)774–780.

    Google Scholar 

  26. S. Chopra and M.R. Rao, Facets of thek-partition polytope (June, 1989).

  27. V. Chvátal, W. Cook and M. Hartmann, On cutting-plane proofs in combinatorial optimization, Linear Algebra Appl. 114/115(1989)455–499.

    Google Scholar 

  28. M. Conforti, M.R. Rao and A. Sassano, The equipartition polytope: Part I and II, R.194–195, IASICNR, Roma, Italy (1987).

    Google Scholar 

  29. Y. Crama, P. Hansen and B. Jaumard, The basic algorithm for pseudo-Boolean programming revisited, RUTCOR Research Report 54-88, Rutgers University, New Brunswick, NJ (1988).

    Google Scholar 

  30. P.M. Dearing, P.L. Hammer and B. Simeone, Boolean and graph-theoretic formulations of the simple plant location problem, RUTCOR Research Report 3-88, Rutgers University, New Brunswick, NJ (1988).

    Google Scholar 

  31. J.S. DeCani, Maximum likelihood paired comparison ranking by linear programming, Biometrika 56(1969)537–545.

    Google Scholar 

  32. C. De Simone, The cut polytope and the Boolean quadric polytope, Discr. Math. 79(1990)71–75.

    Google Scholar 

  33. M. Deza and M. Laurent, Facets for the complete cut cone I, Research Memorandum RMI 88-13, Department of Mathematical Engineering, University of Tokyo (1988).

  34. M. Deza and M. Laurent, Facets for the complete cut cone II: Clique-webb inequalities, Document du Lamsade n. 57, Université Paris Dauphine (1989).

  35. M. Deza and M. Laurent, New results on facets of the cut cone, Report No. B-227, Department of Information Sciences, Tokyo Institute of Technology (1989).

  36. M. Deza, C. De Simone and M. Laurent, Collapsing and lifting for the cut cone, IASI Report No. 265, Rome (1989).

  37. M. Deza, M. Grötschel and M. Laurent, Clique-webb facets for multicut polytopes, Research Report No. 186, Universität Augsburg (1989).

  38. C. Ebenegger, P.L. Hammer and D. de Werra, Pseudo-Boolean functions and stability of graphs, Ann. Discr. Math. 19(1984)83–98.

    Google Scholar 

  39. R.W. Floyd and L. Steinberg, An adaptive algorithm for spatial greyscale, Proc. SID 17(1976)75–77.

    Google Scholar 

  40. J. Fonlupt, A.R. Mahjoub and J.-P. Uhry, Composition of graphs and the bipartite subgraph polytope, Research Report No. 459, Lab. ARTEMIS (IMAG), Univ. de Grenoble (1984).

  41. R. Fortet, L'algèbre de Boole et ses applications en recherche operationelle, Cahiers du Centre d'Etudes de Recherche Operationelle 1(1959)5–36.

    Google Scholar 

  42. A.M.H. Gerards, Testing the odd bicycle wheel inequality for the bipartite subgraph polytope, Math. Oper. Res. 10(1985)359–360.

    Google Scholar 

  43. M. Grötschel, L. Lovász and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica 1(1981)169–197.

    Google Scholar 

  44. M. Grötschel and W.R. Pulleyblank, Weakly bipartite graphs and the max-cut problem, Oper. Res. Lett. 1(1981)23–27.

    Google Scholar 

  45. M. Grötschel and Y. Wakabayashi, Facets of the clique-partitioning polytope, Report No. 6, Institute für Mathematik, Universität Augsburg (1987).

  46. F. Hadlock, Finding a maximum cut of a planar graph in polynomial time, SIAM J. Comput. 4(1975)221–225.

    Google Scholar 

  47. P.L. Hammer, Some network flow problems solved with pseudo-Boolean programming, Oper. Res. 13(1965)388–399.

    Google Scholar 

  48. P.L. Hammer, Plant location — A pseudo-Boolean approach, Israel J. Tech. 6(1968)330–332.

    Google Scholar 

  49. P.L. Hammer, Pseudo-Boolean remarks on balanced graphs, Int. Series Num. Math. 36(1977)69–78.

    Google Scholar 

  50. P.L. Hammer and P. Hansen, Logical relations in quadratic 0–1 programming, Rev. Roum. Math. Pures Appl. 26(1981)421–429.

    Google Scholar 

  51. P.L. Hammer, P. Hansen and B. Simeone, On vertices belonging to all or to no maximum stable sets of a graph, SIAM J. Alg. Discr. Meth. 3(1982)511–522.

    Google Scholar 

  52. P.L. Hammer, P. Hansen and B. Simeone, Roof duality, complementation and persistency in quadratic 0–1 optimization, Math. Progr. 28(1984)121–155.

    Google Scholar 

  53. P.L. Hammer and B. Kalantari, A bound on the roof duality gap, RUTCOR Research Report 46-87, Rutgers University. New Brunswick, NJ (1987).

    Google Scholar 

  54. P.L. Hammer, I. Rosenberg and S. Rudeanu, On the determination of the minima of pseudo-Boolean functions, Stud. Cerc. Mat. 14(1963)359–364, in Romanian.

    Google Scholar 

  55. P.L. Hammer, I. Rosenberg and S. Rudeanu, Application of discrete linear programming to the minimization of Boolean functions, Rev. Roum. Math. Pures Appl. 8(1963)459–475, in Russian.

    Google Scholar 

  56. P.L. Hammer and B. Simeone, Quadratic functions on binary variables, RUTCOR Research Report 20-87, Rutgers University, New Brunswick, NJ (1987).

    Google Scholar 

  57. P. Hansen, Methods of nonlinear 0–1 programming, Ann. Discr. Math. 5(1979)53–70.

    Google Scholar 

  58. P. Hansen, S.H. Lu and B. Simeone, On the equivalence of paved-duality and standard linearization in nonlinear optimization, Discr. Appl. Math., to appear.

  59. F. Harary, On the notion of balance of a signed graph, Michigan Math. J. 2(1953/54)143–146.

    Google Scholar 

  60. J.J. Hopfield, Artificial neural networks, IEEE Circuits Dev. Mag. 4(1988)3–10.

    Google Scholar 

  61. O.H. Ibarra and S.K. Sahni, Polynomially complete fault detection problems, IEEE Trans. Comput. C-24(1975)242–249.

    Google Scholar 

  62. J.F. Jarvis, C.N. Júdice and W.H. Ninke, A survey of techniques for the display of continuous tone pictures on bilevel displays, Comput. Graphics Image Proc. 5(1976)13–40.

    Google Scholar 

  63. R.M. Karp, Reducibility among combinatorial problems,Complexity of Computer Computations, ed. R.E. Miller and J.W. Thatcher (Plenum, New York, 1972), pp. 85–103.

    Google Scholar 

  64. A.V. Karzanov, Metrics and undirected cuts, Math. Progr. 32(1985)183–198.

    Google Scholar 

  65. D.J. Laughhunn, Quadratic binary programming with applications to capital budgeting problems, Oper. Res. 18(1970)454–461.

    Google Scholar 

  66. S.H. Lu and A.C. Williams, Roof duality for 0–1 nonlinear optimization, Math. Progr. 37(1987)357–360.

    Google Scholar 

  67. S.H. Lu and A.C. Williams, Roof duality and linear relaxation for quadratic and polynomial 0–1 optimization, RUTCOR Research Report 8-87, Rutgers University, New Brunswick, NJ (1987).

    Google Scholar 

  68. G.I. Orlova and Y.G. Dorfman, Finding the maximum cut in a graph, Izv. Akad. Nauk SSSR 72(1975)155–159, in Russian [English transl.: Eng. Cybernetics 10(1975)502–506].

    Google Scholar 

  69. M. Padberg, The Boolean quadric polytope: Some characteristics, facets and relatives, Math. Progr. 45(1989)139–171.

    Google Scholar 

  70. S.G. Papaioannou, Optimal test generation in combinatorial networks by pseudo-Boolean programming, IEEE Trans. Comput. C-26(1977)553–560.

    Google Scholar 

  71. L. Personnaz, I. Guyon and G. Dreyfus, Collective computational properties of neural networks: New learning mechanisms, Phys. Rev. A34(1986)4217–4228.

    Google Scholar 

  72. J.C. Picard and H.D. Ratliff, A cut approach to the rectilinear facility location problem, Oper. Res. 26(1978)422–433.

    Google Scholar 

  73. J. Rhys, A selection problem of shared fixed costs and networks, Manag. Sci. 17(1970)200–207.

    Google Scholar 

  74. P.D. Seymour, Matroids and multicommodity flows, Eur. J. Combinatorics 2(1981)257–290.

    Google Scholar 

  75. B. Simeone, Consistency of quadratic Boolean equations and the König-Egerváry property for graphs, Ann. Discr. Math. 25(1985)281–290.

    Google Scholar 

  76. S.R. Sreinberg, Biomedical image processing, IEEE Computer 15(1982)47–56.

    Google Scholar 

  77. H.S. Stone, Multiprocessing scheduling with the aid of network flow algorithms, IEEE Trans. Software Eng. SE-3(1977)85–93.

    Google Scholar 

  78. H.S. Stone, Program assignment in three-processor systems and tricutset partitioning of graphs, Technical Report No. ECE-CS-77-7, Department of Electrical and Computer Engineering, University of Massachusetts, Amherst (1977).

    Google Scholar 

  79. H.S. Stone, Critical load factors in two-processor distributed systems, IEEE Trans. Software Eng. SE-4(1978)254–258.

    Google Scholar 

  80. A. Warszawski, Pseudo-Boolean solutions to multidimensional location problems, Oper. Res. 22(1974)1081–1085.

    Google Scholar 

  81. A.C. Williams, Quadratic 0–1 programming using the roof dual with computational results, RUTCOR Research Report 8-85, Rutgers University, New Brunswick, NJ (1985).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. DIMACS and RUTCOR, Rutgers University, 08903, New Brunswick, NJ, USA

    Endre Boros

  2. RUTCOR, Rutgers University, 08903, New Brunswick, NJ, USA

    Peter L. Hammer

Authors
  1. Endre Boros
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Peter L. Hammer
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Boros, E., Hammer, P.L. The max-cut problem and quadratic 0–1 optimization; polyhedral aspects, relaxations and bounds. Ann Oper Res 33, 151–180 (1991). https://doi.org/10.1007/BF02115753

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02115753

Keywords

Search

Navigation