NYC Photo
A continuous-time approach to constraint satisfaction: Optimization hardness as transient chaos

Young Researchers Team Grant: PN-II-RU-2011-TE-3-0121

contract number: 46/2011

Sponsored by the Romanian National Authority for Scientific Research CNCS-UEFISCDI

Project director: Dr. Mária Ercsey-Ravasz


Research topic:

Constraint satisfaction problems (such as Boolean satisfiability) constitute one of the hardest classes of optimization problems with many applications in technology and industry. Understanding why these problems are hard is crucially important for the development of efficient algorithms. Recently we provided an exact mapping of Boolean satisfiability (k-SAT) into a deterministic continuous-time dynamical system (CTDS) with a unique correspondence between its set of attractors and the k-SAT solutions. We have shown that optimization hardness is fundamentally equivalent to the phenomenon of chaos and turbulence: after a critical constraint density is reached, the trajectories become transiently chaotic before finding the solutions, signaling the appearance of optimization hardness. In this project we explore this revolutionary new connection between traditionally separate fields. Our main objective is to analyze optimization hardness in constraint satisfaction using nonlinear dynamical systems theory. However, Boolean satisfiability being an NP-complete problem it has applications in almost every field of science and industry, this way our methods can be applied in many different research domains.


Aim I: Understanding optimization hardness by studying chaotic properties of the CTDS.

A: Studying the chaotic phase transition appearing in NP-complete problems.

B: Studying the chaotic behavior of locked occupation problems, these being considered the hardest class of constraint satisfaction problems.

C: Distinguishing hard-SAT formulas characterized by long chaotic transients from permanently chaotic UNSAT formulas.

Aim II: Developing a Cellular Nonlinear Network (CNN) model for solving satisfiability problems.

A: Developing a Cellular Neural Network model for solving SAT problems.

B: Studying the effect of noise on these analog algorithms.


Phase I (2011 October-December): Budget: 50,040 RON

- Aim IIA has been started: the mathematical CNN model has been developed

Report I

Phase II (2012): Budget: 273,480 RON

- Aim IA has been started: first observations have shown that the chaotic phase transition appears in SAT problems at a relatively small constraint density.

- Aim IIA has been completed: the properties of the CNN model has been studied both mathematically and with simulations; Its efficiency has been tested.

- Aim IB has been completed: the Sudoku game was studied as a well known example of locked occupation problems. Its transient chaotic properties were used to develop a hardness measure for the puzzles.

Report II

Phase III (2013): Budget: 348,480 RON

- Aim IA has continued: many time consuming simulations had to be implemented.

- Aim IIB has been started: the effects of noise were studied on the dynamics by simulating stochastic differential equations. Both the original and the CNN system was shown to be robust to white and coloured noise.

Report III

Phase IV (2014 January-September): Budget: 248,000 RON

- Aim IA has been completed: the appearance of chaos has been more deeply understood and explained. Results are prepared to eb published.

- Aim IC has been completed: an algorithm was developed and tested for solving the max-SAT problem (identifying the maximum number of satisfiable constraints in UNSAT problems).

- Aim IIB has been completed: the results related to noise effects were published.

Final Sintetic Report

Extra research activities:

Besides the planned activities the group had the opportunity to participate in several international research collaborations which resulted in excellent publications (Science, Nature Communications etc., see publication list).

ISI Journal articles published during the project:

- R. Sumi, B. Molnar, M. Ercsey-Ravasz, "Robust optimization with transiently chaotic dynamical systems", European Physics Letters, 106, 40002 (2014).

- Y. Ren, M. Ercsey-Ravasz, P. Wang, M.C. Gonzalez, Z. Toroczkai, "Modelling roadway network traffic using a radiation model based on temporal ranges", Nature Communications, 5, 5347 (2014)

- N.T. Markov, M. Ercsey-Ravasz, D.C. Van Essen, K. Knoblauch, Z. Toroczkai, H. Kennedy, "Cortical High-density Counter-stream Architectures", Science, 342, 1238406, 2013 doi:10.1126/science.1238406

- M. Ercsey-Ravasz, Z. Toroczkai, "The Chaos Within Sudoku", Nature Scientific Reports 2, 755 (2012) doi:10.1038/srep00725

- M. Ercsey-Ravasz, R. Lichtenwalter, N.W. Chawla, Z. Toroczkai, "Range-limited Centrality Measures in Non-weighted and Weighted Complex Networks, Physical Review E 85, 066103 (2012). arxiv:1111.5382

- M. Ercsey-Ravasz, Z. Toroczkai, Z. Lakner, J. Baranyi, "Complexity of the International Agro-Food Trade Network", PLoS ONE 7(5), e37810 (2012). doi:10.1371/journal.pone.0037810

ISI Conference Proceedings:

- B. Molnár, M. Ercsey-Ravasz, "Analog dynamics for solving max-SAT problems", Proceedings of CNNA 2014, Notre Dame, IN, USA (2014)

- B. Molnár, R. Sumi, M. Ercsey-Ravasz, "A CNN SAT-solver robust to noise", Proceedings of CNNA 2014, Notre Dame, IN, USA (2014)

- K. Knoblauch, M. Ercsey-Ravasz, H. Kennedy, Z. Toroczkai, “The Brain in Space”, Proc. of IPSEN, Paris, May (2014).

- B. Molnár, M. Ercsey-Ravasz, Z. Toroczkai, "Continuous-time Neural Networks Without Local Traps for Solving Boolean Satisfiability", Proceedings of CNNA 2012, p. 4012, Torino, Italy (2012)

Book chapters:

- M. Ercsey-Ravasz, Z. Toroczkai, "Dontesek fizikaja es rejtvenyek kaosza" ("Physics of decision making and chaos of puzzles") in A fizika, matematika es muveszet talalkozasa az oktatasban, kutatasban (Physics, mathematics and arts in education and research), Ed.: A. Juhasz, T. Tel, Publisher: Science Department of the Eotvos Lorand University, Hungary, 2013.

Other publications:

- M. Ercsey-Ravasz, Z. Toroczkai, "A donteshozatal es a Sudoku kaosza" ("The Chaos Within Sudoku and Decision Making"), Termeszet Vilaga (World of Nature), invited paper in the special issue "Kaosz, Kornyezet, Komplexitas" ("Chaos, Environment, Complexity"), Budapest, Hungary, p. 122, 2013

Previous publications relevant to the project:

- M. Ercsey-Ravasz, Z. Toroczkai, "Optimization Hardness as Transient Chaos in an Analog Approach to Constraint Satisfaction", Nature Physics 7, 966 (2011) arxiv:1208.0526

Conferences, Workshops, Invited seminars:

- M. Ercsey-Ravasz “Analog approaches to hard optimization: from Sudoku to CNNs” (oral presentation), Statistical Mechanics of Unsatisfiability and Glasses, Mariehamn, Finland, 23-26 May, 2012

- R. Sumi "Chaotic phase transition in an analog approach to constraint satisfaction" (oral presentation), CHAOS 2012 -5th Chaotic Modeling and Simulation International Conference , Athen, Greece, 12-15 June, 2012

- M. Ercsey-Ravasz "Döntések fizikája és rejtvények káosza" ("Physics of decisions and chaos of puzzles")(oral presentation), A fizika, matematika és művészet találkozása az oktatásban (Physics, mathematics and arts in high school) Tg. Mures, Romania, 15 August, 2012

- M. Ercsey-Ravasz “Solving constraint satisfaction problems via transiently chaotic analog systems and CNN dynamics” (invited talk), CNNA 2012, Torino, Italy (2012)

- B. Molnár, "Continuous-time Neural Networks Without Local Traps for Solving Boolean Satisfiability" (oral presentation), CNNA 2012, Torino, Italy (2012)

- M. Ercsey-Ravasz "Asymmetric neural networks for solving constraint satisfaction", invited seminar at the Information Technology Department of the Pazmany Peter Catholic University, Hungary,22 February, 2013

- R. Sumi participated on the Summer Programming and tUning Massively Parallel systems (PUMPS) Summer School, Barcelona, July 2013.

- M. Ercsey-Ravasz, "The highly connected brain", invited seminar, Harvard Medical School, Beth Israel Deaconess Medical Center, Boston, USA, 29 October 2013

Dissemination activities:

We consider it important to reach out to the general public and especially highschool students.

- Maria Ercsey-Ravasz gave a talk on the "Weekend for Hungarian High-school students" organized by Babes-Bolyai University, with title: "Kaosz a Sudokuban" ("The Chaos Within sudoku"), October 11 2013

- Maria Ercsey-Ravasz gave a talk on the "Weekend for Hungarian High-school students" organized by Babes-Bolyai University, with title: "Fizika a majmok agyaban" ("Physics in the brain of monkeys"), October 12 2013

- Botond Molnar gave a talk on the "Weekend for Hungarian High-school students" organized by Babes-Bolyai University, with title: "Analog szamitogepek" ("Analog computing"), October 12 2013

-Maria Ercsey-Ravasz gave a talk with title "The chaos within Sudoku" to the participants of the Scientific Conference of Highschool Students, May 2013

-Maria Ercsey-Ravasz gave a talk at a conference organized for highschool teachers in Transylvania: "Döntések fizikája és rejtvények káosza" ("Physics of decisions and chaos of puzzles"), A fizika, matematika és művészet találkozása az oktatásban (Physics, mathematics and arts in high school) Tg. Mures, Romania, August 15, 2012. She also wrote an article with the same title in the proceedings of this conference, which will reach highschool teachers from all over Trasylvania.

-We participated on the conference "Vandoregyetem" organized for college students.

-Maria Ercsey-Ravasz was invited to the Unitarian Highschool Janos Zsigmond, where she gave a talk with title "This Is All Physics".

-Botond Molnar and Maria Ercsey-Ravasz have also gave disseminating talks to the highschool students who participated on the Vermes Miklos Physics Competition.

The heavily connected brain - Cortical high-density counterstream architectures

Background.The cerebral cortex is divisible into many individual areas, each exhibiting distinct connectivity profiles, architecture, and physiological characteristics. Interactions among cortical areas underlie higher sensory, motor, and cognitive functions. Graph theory provides an important framework for understanding network properties of the interareal weighted and directed connectivity matrix reported in recent studies.Density and topology of the cortical graph. Figure (Left) The 66% density of the cortical matrix (black triangle) is considerably greater than in previous reports (colored points) and is inconsistent with a small-world network. (Right) A bow-tie representation of the high-density cortical matrix. The high-efficiency cortical core has defined relations with the cortical periphery in the two fans. Advances. We derive an exponential distance rule that predicts many binary and weighted features of the cortical network, including efficiency of information transfer, the high specificity of long-distance compared to short-distance connections, wire length minimization, and the existence of a highly interconnected cortical core. We propose a bow-tie representation of the cortex, which combines these features with hierarchical processing. Outlook. The exponential distance rule has important implications for understanding scaling properties of the cortex and developing future large-scale dynamic models of the cortex.

- N.T. Markov, M. Ercsey-Ravasz, D.C. Van Essen, K. Knoblauch, Z. Toroczkai, H. Kennedy, "Cortical High-density Counter-stream Architectures", Science, 342, 1238406, 2013 doi:10.1126/science.1238406