Optimization Online


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

Zachary Steever(zjsteeve***at***buffalo.edu)
Chase Murray(cmurray3***at***buffalo.edu)
Junsong Yuan(jsyuan***at***buffalo.edu)
Mark Karwan(mkarwan***at***buffalo.edu)
Marco Luebbecke(marco.luebbecke***at***rwth-aachen.de)

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 employed 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 be- tween 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.

Keywords: matrix structure, instance comparison, model comparison, computer vision, feature engineering

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Steever, Zachary and Murray, Chase and Yuan, Junsong and Karwan, Mark and Luebbecke, Marco. An Image-based Approach to Detecting Structural Similarity Among Mixed Integer Programs (April, 2020).

Download: [PDF]

Entry Submitted: 04/20/2020
Entry Accepted: 04/21/2020
Entry Last Modified: 04/20/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society