Top

Published in:

2020 | OriginalPaper | Chapter

Using Integer Programming to Search for Counterexamples: A Case Study

Authors : Giuseppe Lancia, Eleonora Pippia, Franca Rinaldi

Published in: Mathematical Optimization Theory and Operations Research

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

It is known that there exist 4-regular, 1-tough graphs which are non-hamiltonian. The smallest such graph known has \(n=18\) nodes and was found by Bauer et al., who conjectured that all 4-regular, 1-tough graphs with \(n\le 17\) are hamiltonian. They in fact proved that this is true for \(n\le 15\), but left open the possibility of non-hamiltonian graphs of 16 or 17 nodes. By using ILP for modeling a counterexample, and then finding out that the model has no solutions, we give an algorithmic proof that their conjecture was indeed correct.

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 An Extension of the Das and Mathieu QPTAS to the Case of Polylog Capacity Constrained CVRP in Metric Spaces of a Fixed Doubling Dimension

next chapter On Asymptotically Optimal Solvability of Max m-k-Cycles Cover Problem in a Normed Space

Appel, K., Haken, W.: Every planar map is four colorable. I. Discharging. Illinois J. Math. 21(3), 429–490 (1977)MathSciNetCrossRef

Bauer, D., Hakimi, S.L., Schmeichel, E.: Recognizing tough graphs is NP-hard. Discrete Appl. Math 28, 191–195 (1990)MathSciNetCrossRef

Bauer, D., Broersma, H.J., Schmeichel, E.: Toughness in graphs - a survey. Graphs Comb. 22, 1–35 (2006)MathSciNetCrossRef

Bauer, D., Broersma, H.J., Veldman, H.J.: On smallest nonhamiltonian regular tough graphs. Congressus Numerantium 70, 95–98 (1990)MathSciNetMATH

Bauer, D., Broersma, H.J., Veldman, H.J.: Not every 2-tough graph is hamiltonian. Discrete Appl. Math 99, 317–321 (2000)MathSciNetCrossRef

Broersma, H.J.: How tough is toughness? Bull. Eur. Assoc. Theoret. Comput. Sci. 117, 28–52 (2015)MathSciNetMATH

Chvátal, V.: Tough graphs and hamiltonian circuits. Discrete Math. 5, 215–228 (1973)MathSciNetCrossRef

DeLeon, M.: A study of sufficient conditions for hamiltonian cycles. Rose-Hulman Und. Math. J. 1(1), 1–19 (2000)

Desrosiers, J., Lübbecke, M.E.: Branch-Price-and-Cut Algorithms, in the Wiley Encyclopedia of Operations Research and Management Science. Wiley, Chichester (2010)

10.

Gamrath, G., et al.: The SCIP Optimization Suite 3.2.1, ZIB-Report, pp. 15–60 (2016)

11.

Hilbig, F.: Kantenstrukturen in nichthamiltonschen Graphen. Ph.D. thesis, Technische Universït at Berlin (1986)

12.

Hoffman, A.J., Singleton, R.R.: On Moore graphs of diameter two and three. IBM J. Res. Dev. 4, 497–504 (1960)CrossRef

13.

Margot, F.: Symmetry in integer linear programming. In: Jünger, M., et al. (eds.) 50 Years of Integer Programming 1958-2008, pp. 647–686. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-540-68279-0_17CrossRefMATH

14.

McKay, B.D., Piperno, A.: Practical graph isomorphism, II. J. Symbolic Comput. 60, 94–112 (2014)MathSciNetCrossRef

15.

McKay, B.D., Piperno, A.: nauty and Traces User’s Guide (Version 2.6) (2016)

16.

Mitchell, J.E.: Branch-and-cut algorithms for combinatorial optimization problems. In: Pardalos, P.M., Resende, M.G.C. (eds.) Handbook of Applied Optimization, pp. 65–77. Oxford University Press, Oxford (2002)

17.

Ostrowski, J., Linderoth, J., Rossi, F., Smriglio, S.: Orbital branching. Math. Program. 126(1), 147–178 (2011)MathSciNetCrossRef

18.

Pfetsch, M.E., Rehn, T.: A computational comparison of symmetry handling methods for mixed integer programs (2015). http://www.optimization-online.org

19.

Skiena, S.S.: The Algorithm Design Manual. Springer, London (2008). https://doi.org/10.1007/978-1-84800-070-4CrossRefMATH

Title: Using Integer Programming to Search for Counterexamples: A Case Study
Authors: Giuseppe Lancia
Eleonora Pippia
Franca Rinaldi
Publisher: Springer International Publishing
Book: Mathematical Optimization Theory and Operations Research
Print ISBN: 978-3-030-49987-7

Electronic ISBN: 978-3-030-49988-4

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-49988-4_5

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner