Pierre Hansen, Mustapha Aouchiche, Gilles Caporossi, Alain Hertz, Cherif Sellal



Mixed Integer Programming and Extremal Chemical Graphs

pdf PDF


Two systems called AutoGraphiX and ChemoGraphiX are proposed for datamining chemical graphs with extremal values of one or several graphical invariants. AutoGraphiX is based on the variable neighborhood search heuristic and ChemoGraphiX on mixed integer programming.


Chemical graphs, Mixed integer programming, Metaheuristic, Graphical invariant


[1] M. Aouchiche. Comparaison automatis´ee d’invariants en th´eorie des graphes. PhD Thesis, ´E cole Polytechnique de Montr´eal, February 2006.

[2] M. Aouchiche, J.-M. Bonnefoy, A. Fidahoussen, G. Caporossi, P. Hansen, L. Hiesse, J. Lacher´e and A. Monhait. Variable neighborhood search for extremal graphs. 14. The AutoGraphiX 2 system. In L. Liberti and N. Maculan (editors), Global Optimization: From Theory to Implementation, Springer (2006) 281–310.

[3] M. Aouchiche, G. Caporossi and P. Hansen, Variable neighborhood search for extremal graphs 20. Automated comparison of graph invariants. Match Commun. Math. Comput. Chem. 58 (2007) 365–384.

[4] Aouchiche M, Caporossi G, Hansen P, Lucas C (2013) Variable Neighborhood Search for Extremal Graphs. 28: AutoGraphiX After Fifteen Years Les Cahiers du GERAD, G-2013-12.

[5] E. K. Burke and G. Kendall, Search methodologies. Introductory tutorials in optimization and decision support techniques. Springer, Berlin, 2005.

[6] E. Camby, J. Cardinal, S. Fiorini, O. Schaudt, The price of connectivity for vertex cover, Discrete mathematics and theoretical computer science 16 (1), 207–224 (2014).

[7] G. Caporossi and P. Hansen, A learning optimization algorithm in Graph Theory. Versatile Search for extremal graphs using a learning algorithm. Lecture Notes in Computer Science 7219 (2012) 16–30.

[8] G. Caporossi and P. Hansen. Variable neighborhood search for extremal graphs: V. Three ways to automate finding conjectures. Disc.Math, 276 (2004) 81–94.

[9] G. Caporossi and P. Hansen, Variable neighborhood search for extremal graphs: I. The Auto- GraphiX system. Disc. Math. 212 (2000) 29–44.

[10] G. Caporossi and P. Hansen, Finding relations in polynomial time. In Proceedings of the XVIth International Joint Conference on Artificial Intelligence (Stockholm, 1999), vol. 2, 580–585.

[11] J. Christophe, S. Dewez, J.-P. Doignon, G. Fasbender, P. Gr´egoire, D. Huygens, M. Labb´e, S. Elloumi, H. M´elot and H. Yaman, Linear inequalities among graph invariants: using GraPHedron to uncover optimal relationships. Networks 52 (2008) 287–298.

[12] F. Glover and G. Kochenberger, (Eds.), Handbook of metaheuristics. Kluwer, Amsterdam, 2003.

[13] I. Gutman and N. Trinajsti´c, Graph theory and molecular orbitals. Total -electron energy of alternant hydrocarbons, Chemical Physics Letters 17 (4) 535–538 (1972).

[14] I. Gutman, O. Miljkovi´c, G. Caporossi and P. Hansen, Alkanes with small and large Randi´c connectivity indices, Chemical Physics Letters 306 (5) 366–372 (1999).

[15] P. Hansen, A. Hertz, C. Sellal, D. Vukiˇcevi´c, M. Aouchiche, G. Caporossi, Edge Realizability of Connected Simple Graphs. MATCH Commun. Math. Comput. Chem. 78 (2017) 689–712.

[16] P. Hansen and N. Mladenovi´c, Variable neighborhood search. In [12], 145–184.

[17] P. Hansen and N. Mladenovi´c, Variable neighborhood search: principles and applications. European Journal of Operational Research, 130 (2001) 449–467.

[18] P. Hansen and N. Mladenovi´c, Developments of variable neighborhood search. In C. Ribeiro and P. Hansen (Eds.), Essays, surveys in metaheuristics. Kluwer, Amsterdam, 2001, 415–440.

[19] P. Hansen and N.Mladenovi´c, An introduction to variable neighborhood search. In S. Voss et al. (Eds.), Metaheuristics, advances, trends in local search paradigms for optimization. Kluwer, Amsterdam, 1999, 433–458.

[20] P. Hansen, N. Mladenovi´c and J. A. Moreno P´erez, Variable neighborhood search: methods and applications. Ann. Oper. Res. 175 (2010) 367–407.

[21] S. C. D. Kirkpatrick, Jr. Gellatt and P. Vecchi, Optimization by simulated annealing. Science 220 (1983) 671–680.

[22] X. Li and I. Gutman, Mathematical aspects of Randi´c-type molecular structure descriptors, Mathematical Chemistry Monographs, University of Kragujevac, 2006.

[23] N. Mladenovi´c and P. Hansen, Variable neighborhood search. Computers and Operations Research, 24 (1997) 1097–1100.

[24] M. Randi´c, Characterization of molecular branching, Journal of the American Chemical Society 97 6609–6615 (1975).

[25] C. R. Reeves, (Ed.), Modern heuristic techniques for combinatorial problems. Blackwell Scientific, Oxford, 1993.

[26] N. Sloane, The on-line encyclopedia of integer sequences. Available at http://www.research.att.com/minjas/sequences/.

[27] D. Vukiˇcevi´c and M. Gaˇsperov, Bond additive modeling 1. Adriatic indices, Croatica Chemica Acta 83 243–260 (2010).

Cite this paper

Pierre Hansen, Mustapha Aouchiche, Gilles Caporossi, Alain Hertz, Cherif Sellal. (2018) Mixed Integer Programming and Extremal Chemical Graphs. International Journal of Chemistry and Chemical Engineering Systems, 3, 22-30


Copyright © 2018 Author(s) retain the copyright of this article.
This article is published under the terms of the Creative Commons Attribution License 4.0