Timezone: »

 
Hierarchical Decomposition Framework for Feasibility-hard Combinatorial Optimization
Hanbum Ko · Minu Kim · Han-Seul Jeong · Sunghoon Hong · Deunsol Yoon · Youngjoon Park · Woohyung Lim · Honglak Lee · Moontae Lee · Kanghoon Lee · Sungbin Lim · Sungryull Sohn

@
in Sampling and Optimization in Discrete Space »
Event URL: https://openreview.net/forum?id=vnpMMjYnA2 »

Combinatorial optimization (CO) is a widely-applied method for addressing a variety of real-world optimization problems. However, due to the NP-hard nature of these problems, complex problem-specific heuristics are often required to tackle them at real-world scales. Neural combinatorial optimization has emerged as an effective approach to tackle CO problems, but it often requires the pre-computed optimal solution or a hand-designed process to ensure the model to generate a feasible solution, which may not be available in many real-world CO problems. We propose the hierarchical combinatorial optimizer (HCO) that does not rely on such restrictive assumptions. HCO decomposes the given CO problem into multiple sub-problems on different scales with smaller search spaces, where each sub-problem can be optimized separately and their solutions can be combined to compose the entire solution. Our experiments demonstrate that this hierarchical decomposition facilitates more efficient learning and stronger generalization capabilities, outperforming traditional heuristic and mathematical optimization algorithms.

Author Information

Hanbum Ko (Ulsan National Institute of Science and Technology)
Minu Kim (KAIST)
Han-Seul Jeong (LG AI Research)
Sunghoon Hong (LG AI Research)
Deunsol Yoon (LG AI Research)
Youngjoon Park (LG AI Research)
Woohyung Lim (LG AI Research)
Honglak Lee (LG AI Research / U. Michigan)
Moontae Lee (University of Illinois at Chicago)
Kanghoon Lee (LG AI Research)
Sungbin Lim (Korea University)
Sungryull Sohn (LG AI research center, Ann Arbor)

More from the Same Authors