An Image-Based Approach to Detecting Structural Similarity Among Mixed Integer Programs
提出用数字图像可视化混合整数规划的约束系数矩阵结构，借助计算机视觉技术提取特征并测量相似性，发现不同应用领域的MIP间可能存在结构关联。
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.