web stats
 
   
 
Selected Development Project
 
Project Title

Connecting Theoretical Statistical Physics with Practical Combinatorial Optimization Problems
理論性統計物理與典型組合優化問題的結合
 
Principal Investigator Dr YEUNG Chi Ho
 
Area of Research Project
Science and Environmental Studies
 
Project Period
From 01/2017 To 12/2019
Objectives
  1. To reveal the energy landscapes of practical small and finite-size combinatorial optimization problems
  2. To understand the physics and the dynamics of non-physics algorithms
  3. To understand problem-specific performances of the physics-inspired algorithms
  4. To connect features in the real variable space which interest optimization researchers, with characteristics in the state space which interest physicists
  5. To convert the newly derived understandings of optimization problems into applications and new algorithms
Methods Used
By making use of the similarity between finding the lowest energy state in physical systems and identifying the optimal solution in optimization problems, we employ methods developed in statistical physics to study practical-size optimization problems and reveal their physical pictures and macroscopic behaviours. We will also employ physics tools to analyse non-physics optimization algorithms introduced in the areas of computer science or applied mathematics, as well as physics-inspired algorithms. Based on the new understandings in the physics of optimization problems and their respective algorithms, new paradigm of optimization will be explored.
Summary of Findings
  • A new methodology to reveal the coarse-grained state space of finite size optimization algorithms
  • Further understandings on the convergence of message passing algorithms on graphs with loops
  • The relationship between microscopic structures called self-sustained clusters and computation hardness of optimization problems
Impact
  1. Generic optimization improvement over existing approaches, regardless of physics or non-physics origins
  2. Further understandings of non-physics optimization methodologies using techniques developed in statistical physics
  3. New understandings of problem-specific effectiveness of optimization algorithms
  4. Newly derived physics-inspired optimization paradigm and algorithms applicable on other general optimization problems
  5. New understanding and algorithms on optimization problems may in turn impact on the study of physical systems
Selected Output
Rocchi, J., Saad D., Yeung C.H., Self-sustained clusters as drivers of computational hardness in p-spin models, Physical Review B 96 (2), 024415 (2017).
Biography of Principal Investigator

Dr Yeung Chi Ho is an Assistant Professor of Department of Science and Environmental Studies at The Education University of Hong Kong. His research interests include statistical physics, physics of disordered systems, modelling, transportation networks, complex and social networks, optimization and resource allocations, recommender systems, interdisciplinary applications of statistical physics, and application of technology on education.

Funding Source

General Research Fund