Connecting Theoretical Statistical Physics with Practical Combinatorial Optimization Problems

    Project: Research project

    Project Details


    Optimization corresponds to the task to identify a configuration of variables to maximize or minimize an objective function. It is implicitly implemented in a wide range of daily activities, as well as numerous tasks in research, industry and commerce. Computer scientists, operations researchers and applied mathematicians have devoted great efforts to develop optimization algorithms to tackle specific tasks, and found that some optimization problems are more difficult to solve than the others. Yet, the origins of such difficulties are not fully understood and are not a major interest in conventional studies. Definitely, a clear understanding will lead to stimulating clues to improve optimization algorithms and their ability to tackle hard problems. Physicists play an important role to develop a fundamental understanding of optimization problems by drawing an analogy with physical systems which tend to achieve the state with the lowest energy, analogous to an optimal state. Nevertheless, physicists are interested in aspects of optimization problems that conventional optimization researchers find unrealistic, irrelevant or impractical. This leads to a limited recognition of the physics-based results among conventional optimization researchers and thus, isolated developments in the two individual areas.

    We propose to better integrate and bridge physics and combinatorial optimization problems, by (1) using physical tools to study aspects of optimization problems where optimization researchers find most practical, (2) improving methodologies in both areas instead of improving merely the methodologies from physics, and (3) converting the new understandings into new applications.
    Effective start/end date01/01/1730/06/20