A Graph-Based Approach for Relating Integer Programs

Zachary Steever (), Kyle Hunt (), Mark Karwan (), Junsong Yuan () and Chase C. Murray ()
Additional contact information
Zachary Steever: Philadelphia Eagles, Philadelphia, Pennsylvania 19148
Kyle Hunt: Department of Management Science and Systems, University at Buffalo, Buffalo, New York 14260
Mark Karwan: Department of Industrial & Systems Engineering, University at Buffalo, Buffalo, New York 14260
Junsong Yuan: Department of Computer Science and Engineering, University at Buffalo, Buffalo, New York 14260
Chase C. Murray: Department of Industrial & Systems Engineering, University at Buffalo, Buffalo, New York 14260

INFORMS Journal on Computing, 2024, vol. 36, issue 6, 1715-1736

Abstract: This paper presents a framework for classifying and comparing instances of integer linear programs (ILPs) based on their mathematical structure. It has long been observed that the structure of ILPs can play an important role in determining the effectiveness of certain solution techniques; those that work well for one class of ILPs are often found to be effective in solving similarly structured problems. In this work, the structure of a given ILP instance is captured via a graph-based representation, where decision variables and constraints are described by nodes, and edges denote the presence of decision variables in certain constraints. Using machine learning techniques for graph-structured data, we introduce two approaches for leveraging the graph representations for relating ILPs. In the first approach, a graph convolutional network (GCN) is used to classify ILP graphs as having come from one of a known number of problem classes. The second approach makes use of latent features learned by the GCN to compare ILP graphs to one another directly. As part of the latter approach, we introduce a formal measure of graph-based structural similarity. A series of empirical studies indicate strong performance for both the classification and comparison procedures. Additional properties of ILP graphs, namely, losslessness and permutation invariance, are also explored via computational experiments.

Keywords: model structure; combinatorial optimization; mixed integer programming; neural network (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.0255 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:36:y:2024:i:6:p:1715-1736

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().