An Image-Based Approach to Detecting Structural Similarity Among Mixed Integer Programs
- 1 July 2022
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 34 (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
This publication has 48 references indexed in Scilit:
- Image Classification with the Fisher Vector: Theory and PracticeInternational Journal of Computer Vision, 2013
- The first international nurse rostering competition 2010Annals of Operations Research, 2012
- A branch‐and‐cut algorithm for partition coloringNetworks, 2009
- The vehicle routing problem: A taxonomic reviewComputers & Industrial Engineering, 2009
- gnuplot 4.0: a portable interactive plotting utilityJournal of Applied Econometrics, 2006
- Resource-constrained project scheduling: Notation, classification, models, and methodsEuropean Journal of Operational Research, 1999
- A neural network approach to facility layout problemsEuropean Journal of Operational Research, 1996
- Neural Networks for Optimization Problems with Inequality Constraints: The Knapsack ProblemNeural Computation, 1993
- A sufficient condition for a matrix to be totally unimodularNetworks, 1973
- Partitioning procedures for solving mixed-variables programming problemsNumerische Mathematik, 1962