nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Exact Separation of k-Projection Polytope Constraints

verfasst von : Elspeth Adams, Miguel F. Anjos

Erschienen in: Modeling and Optimization: Theory and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

A critical step of any cutting plane algorithm is to find valid inequalities, or more generally valid constraints, that improve the current relaxation of the integer-constrained problem. We consider the k-projection polytope constraints that are a family of constraints based on an inner description of the cut polytope of size k and are applied to k × k principal minors of the matrix variable of a semidefinite optimization relaxation. We propose a bilevel second order cone optimization approach to find the maximally violated k-projection polytope constraint according to a specific depth measure, and reformulate the bilevel problem as a single-level mixed binary second order cone optimization problem. We report computational results using the proposed approach within a cutting plane algorithm on instances of max-cut with 500 and 600 nodes.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Projected Semi-Stochastic Gradient Descent Method with Mini-Batch Scheme Under Weak Strong Convexity Assumption

Nächstes Kapitel Univariate Polynomial Optimization with Sum-of-Squares Interpolants

Adams, E.: A novel approach to tightening semidefinite relaxations for certain combinatorial problems. PhD thesis, Polytechnique Montreal (2015)

Adams, E., Anjos, M.F., Rendl, F., Wiegele, A.: A hierarchy of subgraph projection-based semidefinite relaxations for some NP-hard graph optimization problems. INFOR Inf. Syst. Oper. Res. 53(1), 40–48 (2015)MathSciNet

Amaldi, E., Coniglio, S., Gualandi, S.: Coordinated cutting plane generation via multi-objective separation. Math. Program. 143(1–2), 87–110 (2014)CrossRefMathSciNetMATH

Applegate, D., Bixby, R., Chvátal, V., Cook, W.: The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton (2006)MATH

Balas, E., Ceria, S., Cornuéjols, G.: A lift-and-project cutting plane algorithm for mixed 0–1 programs. Math. Program. 58(1–3), 295–324 (1993)CrossRefMathSciNetMATH

Caprara, A., Fischetti, M.: {0, 1/2}-Chvátal-Gomory cuts. Math. Program. 74(3), 221–235 (1996)

Caprara, A., Fischetti, M.: Branch-and-cut algorithms. Annotated Bibliographies in Combinatorial Optimization, pp. 45–64. Wiley, Chichester (1997)

Caprara, A., Letchford, A.N.: On the separation of split cuts and related inequalities. Math. Program. 94(2–3), 279–294 (2003)CrossRefMathSciNetMATH

Caprara, A., Fischetti, M., Letchford, A.N.: On the separation of maximally violated mod-k cuts. Math. Program. 87(1), 37–56 (2000)CrossRefMathSciNetMATH

10.

Chvátal, V.: Edmonds polytopes and a hierarchy of combinatorial problems. Discret. Math. 4(4), 305–337 (1973)CrossRefMathSciNetMATH

11.

Cook, W., Kannan, R., Schrijver, A.: Chvátal closures for mixed integer programming problems. Math. Program. 47(1–3), 155–174 (1990)CrossRefMATH

12.

Dantzig, G., Fulkerson, R., Johnson, S.: Solution of a large-scale traveling-salesman problem. J. Oper. Res. Soc. Am. 2(4), 393–410 (1954)MathSciNet

13.

Delorme, C., Poljak, S.: Laplacian eigenvalues and the maximum cut problem. Math. Program. 62(3, Ser. A), 557–574 (1993)

14.

Eisenbrand, F.: Note–on the membership problem for the elementary closure of a polyhedron. Combinatorica 19(2), 297–300 (1999)CrossRefMathSciNetMATH

15.

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. 105(2–3, Ser. B), 451–469 (2006)

16.

Gomory, R.E.: An algorithm for integer solutions to linear programs. Recent Adv. Math. Program. 64, 260–302 (1963)MathSciNetMATH

17.

Grishukhin, V.P.: All facets of the cut cone C _n for n = 7 are known. Eur. J. Comb. 11(2), 115–117 (1990)CrossRefMathSciNetMATH

18.

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

19.

Helmberg, C., Rendl, F., Vanderbei, R.J., Wolkowicz, H.: An interior-point method for semidefinite programming. SIAM J. Optim. 6(2), 342–361 (1996)CrossRefMathSciNetMATH

20.

Krislock, N., Malick, J., Roupin, F.: Improved semidefinite bounding procedure for solving max-cut problems to optimality. Math. Program. 143(1–2), 61–86 (2014)CrossRefMathSciNetMATH

21.

Lodi, A., Ralphs, T.K., Woeginger, G.J.: Bilevel programming and the separation problem. Math. Program. 146, 437–458 (2014)CrossRefMathSciNetMATH

22.

Marchand, H., Martin, A., Weismantel, R., Wolsey, L.: Cutting planes in integer and mixed integer programming. Discret. Appl. Math. 123(1), 397–446 (2002)CrossRefMathSciNetMATH

23.

McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: part I – convex underestimating problems. Math. Program. 10(1), 147–175 (1976)CrossRefMATH

24.

Mitchell, J.E.: Branch-and-cut algorithms for combinatorial optimization problems. In: Handbook of Applied Optimization, pp. 65–77 (2002)

25.

Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization, vol. 18. Wiley, New York (1988)MATH

26.

Padberg, M., Rinaldi, G.: A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev. 33(1), 60–100 (1991)CrossRefMathSciNetMATH

27.

Rendl, F., Rinaldi, G., Wiegele, A.: Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Math. Program. 121(2), 307–335 (2010)CrossRefMathSciNetMATH

28.

Toh, K.-C., Todd, M.J., Tütüncü, R.H.: On the implementation and usage of SDPT3 – a MATLAB software package for semidefinite-quadratic-linear programming, version 4.0. In: Handbook on Semidefinite, Conic and Polynomial Optimization, pp. 715–754. Springer, Boston (2012)

29.

Wiegele, A.: Biq mac library. http://biqmac.uni-klu.ac.at/biqmaclib

30.

Zanette, A., Fischetti, M., Balas, E.: Lexicography and degeneracy: can a pure cutting plane algorithm work? Math. Program. 130(1), 153–176 (2011)CrossRefMathSciNetMATH

Titel: Exact Separation of k-Projection Polytope Constraints
verfasst von: Elspeth Adams
Miguel F. Anjos
Verlag: Springer International Publishing
Buch: Modeling and Optimization: Theory and Applications
Print ISBN: 978-3-319-66615-0

Electronic ISBN: 978-3-319-66616-7

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-66616-7_8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"