An Image-Based Approach to Detecting Structural Similarity Among Mixed Integer Programs

Zachary Steever (), Chase Murray (), Junsong Yuan (), Mark Karwan () and Marco Lübbecke ()
Additional contact information
Zachary Steever: University at Buffalo, The State University of New York, Buffalo, New York 14216
Chase Murray: University at Buffalo, The State University of New York, Buffalo, New York 14216
Junsong Yuan: University at Buffalo, The State University of New York, Buffalo, New York 14216
Mark Karwan: University at Buffalo, The State University of New York, Buffalo, New York 14216
Marco Lübbecke: Lehrstuhl für Operations Research, RWTH Aachen University, 52072 Aachen, Germany

INFORMS Journal on Computing, 2022, vol. 34, issue 4, 1849-1870

Abstract: Operations researchers have long drawn insight from the structure of constraint coefficient matrices (CCMs) for mixed integer programs (MIPs). We propose a new question: Can pictorial representations of CCM structure be used to identify similar MIP models and instances? In this paper, CCM structure is visualized using digital images, and computer vision techniques are used to detect latent structural features therein. The resulting feature vectors are used to measure similarity between images and, consequently, MIPs. An introductory analysis examines a subset of the instances from strIPlib and MIPLIB 2017, two online repositories for MIP instances. Results indicate that structure-based comparisons may allow for relationships to be identified between MIPs from disparate application areas. Additionally, image-based comparisons reveal that ostensibly similar variations of an MIP model may yield instances with markedly different mathematical structures. Summary of Contribution: This paper presents a methodology for comparing mixed integer programs (MIPs) from any research domain based on the structure of the constraint coefficient matrices for one or more instances of a model. Specifically, computer vision and deep learning techniques are used to extract structural features and measure the similarity between these images. This process is agnostic to application area and instead focuses solely on mathematical structure. As a result, this methodology offers a fundamentally new way for operations researchers to view MIP similarity and highlights similarities between research problems that may have previously been viewed as unrelated.

Keywords: matrix structure; instance comparison; model comparison; computer vision; feature engineering (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2021.1117 (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:34:y:2022:i:4:p:1849-1870

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 ().