×

zbMATH — the first resource for mathematics

A note on the 2-circulant inequalities for the MAX-cut problem. (English) Zbl 1452.90269
Summary: The max-cut problem is a much-studied \(\mathcal{N} P\)-hard combinatorial optimisation problem. S. Poljak and D. Turzík [Discrete Math. 108, No. 1–3, 379–392 (1992; Zbl 0769.05059)] found some facet-defining inequalities for this problem, which we call 2-circulant inequalities. Two polynomial-time separation algorithms have been found for these inequalities, but one is very slow and the other is very complicated. We present a third algorithm, which is as fast as the faster of the existing two, but much simpler.
MSC:
90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Software:
Biq Mac
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Balas, E.; Ceria, S.; Cornuéjols, G., A lift-and-project cutting plane algorithm for mixed 01 programs, Math. Program., 58, 295-324, (1993) · Zbl 0796.90041
[2] Barahona, F.; Jünger, M.; Reinelt, G., Experiments in quadratic 0-1 programming, Math. Program., 44, 127-137, (1989) · Zbl 0677.90046
[3] Barahona, F.; Mahjoub, A. R., On the cut polytope, Math. Program., 36, 157-173, (1986) · Zbl 0616.90058
[4] Bonato, T.; Jünger, M.; Reinelt, G.; Rinaldi, G., Lifting and separation procedures for the cut polytope, Math. Program., 146, 351-378, (2014) · Zbl 1297.90133
[5] Caprara, A.; Fischetti, M., \(\{0, \frac{1}{2} \}\)-chvátal-Gomory cuts, Math. Program., 74, 221-235, (1996) · Zbl 0855.90088
[6] Cheng, E., Separating subdivision of bicycle wheel inequalities over cut polytopes, Oper. Res. Lett., 23, 13-19, (1998) · Zbl 0954.90068
[7] Conforti, M.; Cornuéjols, G.; Zambelli, G., Integer programming, (2014), Springer Cham, Switzerland · Zbl 1307.90001
[8] De Simone, C., The cut polytope and the Boolean quadric polytope, Discrete Math., 79, 71-75, (1989) · Zbl 0683.90068
[9] De Simone, C.; Rinaldi, G., A cutting plane algorithm for the MAX-cut problem, Opt. Methods Softw., 3, 195-214, (1994)
[10] Deza, M. M.; Laurent, M., Geometry of cuts and metrics, (1997), Springer-Verlag Berlin · Zbl 0885.52001
[11] Fredman, M. L.; Tarjan, R. E., Fibonacci heaps and their uses in improved network optimization algorithms, J. ACM, 34, 596-615, (1987)
[12] Galli, L.; Kaparis, K.; Letchford, A. N., Gap inequalities for the MAX-cut problem: a cutting-plane algorithm, (Mahjoub, A. R.; Markakis, V.; Milis, I.; Paschos, V. T., Combinatorial Optimization: Proceedings of ISCO 2012, (2012), Springer Berlin), 178-188 · Zbl 1370.90214
[13] Garey, M. R.; Johnson, D. S.; Stockmeyer, L. J., Some simplified \(\mathcal{NP}\)-complete graph problems, Theoret. Comput. Sci., 1, 237-267, (1976) · Zbl 0338.05120
[14] Gerards, A. M.H., Testing the odd bicycle wheel inequalities for the bipartite subgraph polytope, Math. Oper. Res., 10, 359-360, (1985) · Zbl 0578.05057
[15] Gerards, A. H.M.; Schrijver, A. J., Matrices with the edmonds-Johnson property, Combinatorica, 6, 365-379, (1986) · Zbl 0641.05039
[16] Grötschel, M.; Lovász, L.; Schrijver, A. J., Geometric algorithms in combinatorial optimization, (1988), Wiley New York
[17] Helmberg, C.; Rendl, F., Solving quadratic (0,1)-programs by semidefinite programs and cutting planes, Math. Program., 82, 291-315, (1998) · Zbl 0919.90112
[18] Laurent, M., MAX-cut problem, (Dell’Amico, M.; Maffoli, F.; Martello, S., Annotated Bibliographies in Combinatorial Optimization, (1997), Wiley Chichester), 241-259 · Zbl 1068.90517
[19] Laurent, M.; Poljak, S., On a positive semidefinite relaxation of the cut polytope, Linear Algebra Appl., 223/224, 439-461, (1995) · Zbl 0835.90078
[20] Letchford, A. N., On disjunctive cuts for combinatorial optimization, J. Comb. Optim., 5, 299-315, (2001) · Zbl 1078.90039
[21] Letchford, A. N.; Sørensen, M. M., A new separation algorithm for the Boolean quadric and cut polytopes, Discrete Optim., 14, 61-71, (2014) · Zbl 1308.90209
[22] Padberg, M. W., The Boolean quadric polytope: some characteristics, facets and relatives, Math. Program., 45, 139-172, (1989) · Zbl 0675.90056
[23] Palagi, L.; Piccialli, V.; Rendl, F.; Rinaldi, G.; Wiegele, A., Computational approaches to MAX-cut, (Anjos, M. F.; Lasserre, J. B., Handbook on Semidefinite, Conic and Polynomial Optimization, (2012), Springer US Boston, MA), 821-847 · Zbl 1334.90149
[24] Poljak, S.; Turzik, D., MAX-cut in circulant graphs, Discrete Math., 108, 379-392, (1992) · Zbl 0769.05059
[25] Rendl, F.; Rinaldi, G.; Wiegele, A., Solving MAX-cut to optimality by intersecting semidefinite and polyhedral relaxations, Math. Program., 121, 307-335, (2010) · Zbl 1184.90118
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.