Learning Heuristics for Combinatorial Assignment by Optimally Solving Subproblems

Hand-crafting accurate heuristics for optimization problems is often costly due to requiring expert knowledge and time-consuming parameter tuning. Automating this procedure using machine learning has in recent years shown great promise. However, a large number of important problem classes remain unexplored. This paper investigates one such class by exploring learning-based methods for generating heuristics to perform value-maximizing combinatorial assignment (the partitioning of elements among alternatives). In more detail, we use machine learning leveraged by generating and optimally solving subproblems to produce heuristics that can, for example, be used with search algorithms to find feasible solutions of higher quality more quickly. Our results show that our learned heuristics outperform the state of the art in several benchmarks.

Authors

• Fredrik Präntare
• Herman Appelgren
• Mattias Tiger Linköping University
• David Bergström Department of Computer and Information Science, Linköping University, Sweden
• Fredrik Heintz

Keywords

• Operations Research
• Machine Learning
• Deep Learning
• Heuristic
• Search
• Combinatorial Optimization
• Neural Networks
• Inapproximability
• Coalition Formation
• Combinatorial Auctions