Computational Experience with Hypergraph-Based Methods for Automatic Decomposition in Discrete Optimization

摘要

Branch-and-price (BAP) algorithms based on Dantzig-Wolfe decomposition have shown great success in solving mixed integer linear optimization problems (MILPs) with specific identifiable structure. Only recently has there been investigation into the development of a "generic" version of BAP for unstructured MILPs. One of the most important elements required for such a generic BAP algorithm is an automatic method of decomposition. In this paper, we report on preliminary experiments using hypergraph partitioning as a means of performing such automatic decomposition.