Learn to Formulate: A Surrogate Model Framework for Generalized Assignment Problem with Routing Constraints

The generalized assignment problem with routing constraints, for example, the vehicle routing problem, has essential practical relevance. This paper focuses on addressing the complexities of the problem by learning a surrogate model with reduced variables and reconstructed constraints. A surrogate model framework is presented with a class of surrogate models and a learning method to acquire parameters. The paper further provides theoretical results regarding the representational power and statistical properties to explore the effectiveness of this framework. Numerical experiments based on three practical problem classes demonstrate the accuracy and efficiency of the framework. The resulting surrogate models perform comparably to or surpass the state-of-the-art heuristics on average. Our findings provide empirical evidence for the effectiveness of utilizing size-reduced and reconstructed surrogate models to produce high-quality solutions.

History: Accepted by Andrea Lodi, Design & Analysis of Algorithms–Discrete.

Funding: This work was funded by the National Key Research and Development Program of China [Grant 2025YFA1016800], and the National Nature Science Foundation of China [Grant 12320101001].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0736) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2024.0736). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.