Hierarchical Decomposition Framework for Feasibility-Hard Combinatorial Optimization

Abstract

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.