×

A new separation algorithm for the Boolean quadric and cut polytopes. (English) Zbl 1308.90209

Summary: A separation algorithm is a procedure for generating cutting planes. Up to now, only a few polynomial-time separation algorithms were known for the Boolean quadric and cut polytopes. These polytopes arise in connection with zero-one quadratic programming and the max-cut problem, respectively. We present a new algorithm, which separates over a class of valid inequalities that includes all odd bicycle wheel inequalities and \((2p+1,2)\)-circulant inequalities. It exploits, in a non-trivial way, three known results in the literature: one on the separation of \(\{0,\frac{1}{2}\}\)-cuts, one on the symmetries of the polytopes in question, and one on an affine mapping between the polytopes.

MSC:

90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C20 Quadratic programming
90C09 Boolean programming

Software:

BiqMac; Concorde; Biq Mac
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aardal, K.; Weismantel, R., Polyhedral combinatorics, (Dell’Amico, M.; Maffioli, F.; Martello, S., Annotated Bibliographies in Combinatorial Optimization (1997), Wiley: Wiley New York) · Zbl 1068.90500
[2] Cook, W. J., Fifty-plus years of combinatorial integer programming, (Jünger, M.; etal., 50 Years of Integer Programming: 1958-2008 (2010), Springer: Springer Berlin)
[3] Caprara, A.; Fischetti, M., Branch-and-cut algorithms, (Dell’Amico, M.; Maffioli, F.; Martello, S., Annotated Bibliographies in Combinatorial Optimization (1997), Wiley: Wiley New York) · Zbl 1068.90505
[4] Mitchell, J. E., Branch and cut, (Cochran, J. J.; etal., Wiley Encyclopedia of Operations Research and Management Science (2011), Wiley: Wiley New York)
[5] Grötschel, M.; Lovász, L.; Schijver, A., Geometric Algorithms and Combinatorial Optimization (1988), Springer: Springer Heidelberg
[6] Applegate, D.; Bixby, R. E.; Chvátal, V.; Cook, W. J., The Traveling Salesman Problem: A Computational Study (2006), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 1130.90036
[7] Letchford, A. N.; Lodi, A., Mathematical programming approaches to the traveling salesman problem, (Cochran, J. J.; etal., Encyclopedia of Operations Research and Management Science, Vol. 5 (2011), Wiley: Wiley New York)
[8] Padberg, M. W., The Boolean quadric polytope: some characteristics, facets and relatives, Math. Program., 45, 139-172 (1989) · Zbl 0675.90056
[9] Barahona, F.; Mahjoub, A. R., On the cut polytope, Math. Program., 36, 157-173 (1986) · Zbl 0616.90058
[10] Boros, E.; Hammer, P. L., Pseudo-Boolean optimization, Discrete Appl. Math., 123, 155-225 (2002) · Zbl 1076.90032
[11] Deza, M. M.; Laurent, M., Geometry of Cuts and Metrics (1997), Springer: Springer Berlin · Zbl 0885.52001
[12] Barahona, F.; Jünger, M.; Reinelt, G., Experiments in quadratic 0-1 programming, Math. Program., 44, 127-137 (1989) · Zbl 0677.90046
[13] De Simone, C., The cut polytope and the Boolean quadric polytope, Discrete Math., 79, 71-75 (1989) · Zbl 0683.90068
[14] Poljak, S.; Turzik, D., Max-cut in circulant graphs, Discrete Math., 108, 379-392 (1992) · Zbl 0769.05059
[15] Letchford, A. N., On disjunctive cuts for combinatorial optimization, J. Comb. Optim., 5, 299-315 (2001) · Zbl 1078.90039
[16] Caprara, A.; Fischetti, M., \(\{0, \frac{1}{2} \} \)-Chvátal-Gomory cuts, Math. Program., 74, 221-235 (1996) · Zbl 0855.90088
[17] Fortet, R., L’Algèbre de Boole et ses applications en recherche opérationnelle, Cah. Cent. Etud. Rech. Oper., 4, 5-36 (1959) · Zbl 0093.32704
[18] Boros, E.; Hammer, P. L., Cut-polytopes, Boolean quadric polytopes and nonnegative quadratic pseudo-Boolean functions, Math. Oper. Res., 18, 245-253 (1993) · Zbl 0778.90041
[19] Macambira, E. M.; de Souza, C. C., The edge-weighted clique problem: valid inequalities, facets and polyhedral computations, European J. Oper. Res., 123, 346-371 (2000) · Zbl 0961.90067
[20] Sørensen, M. M., New facets and a branch-and-cut algorithm for the weighted clique problem, European J. Oper. Res., 154, 57-70 (2004) · Zbl 1099.90068
[21] Yajima, Y.; Fujie, T., A polyhedral approach for nonconvex quadratic programming problems with box constraints, J. Global Optim., 13, 151-170 (1998) · Zbl 0912.90234
[22] Sherali, H. D.; Fraticelli, B. M.P., Enhancing RLT relaxations via a new class of semidefinite cuts, J. Global Optim., 22, 233-261 (2002) · Zbl 1045.90044
[23] 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
[24] De Simone, C.; Rinaldi, G., A cutting plane algorithm for the max-cut problem, Optim. Methods Softw., 3, 195-214 (1994)
[25] Gruber, G., On semidefinite programming and applications in combinatorial optimization (2000), Department of Mathematics, University of Klagenfurt, (Ph.D. thesis)
[26] Helmberg, C.; Rendl, F., Solving quadratic \((0, 1)\)-programs by semidefinite programs and cutting planes, Math. Program., 82, 291-315 (1998) · Zbl 0919.90112
[27] Laurent, M.; Poljak, S., On a positive semidefinite relaxation of the cut polytope, Linear Algebra Appl., 223-224, 439-461 (1995) · Zbl 0835.90078
[28] 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
[29] Cheng, E., Separating subdivision of bicycle wheel inequalities over cut polytopes, Oper. Res. Lett., 23, 13-19 (1998) · Zbl 0954.90068
[30] Liers, F., Contributions to determining exact ground-states of ising spin-glasses and to their physics (2004), Faculty of Mathematics and Natural Sciences, University of Cologne, (Ph.D. thesis)
[31] Dijkstra, E. W., A note on two problems in connexion with graphs, Numer. Math., 1, 269-271 (1959) · Zbl 0092.16002
[32] Boros, E.; Crama, Y.; Hammer, P. L., Chvátal cuts and odd cycle inequalities in quadratic 0-1 optimization, SIAM J. Discrete Math., 5, 163-177 (1992) · Zbl 0761.90069
[33] Fredman, M. L.; Tarjan, R. E., Fibonacci heaps and their uses in improved network optimization algorithms, J. Assoc. Comput. Mach., 34, 596-615 (1987) · Zbl 1412.68048
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.