Image-based Comparison of Integer Programs (ICIP)

This website serves as a home for research being conducted on Image-based Comparison of Integer Programs, or, ICIP..

In ICIP, mixed integer programs (MIPs) are compared based on the structure of the constraint coefficient matrices (CCMs) for one or more instances of a model. The CCM is the matrix \(\mathbf{A}\) in an integer program of the form: $$\max\{\mathbf{cx} : \mathbf{Ax} \le \mathbf{b}, \mathbf{x} \in \mathbb{Z}^{n}_{+}\}.$$

The methodology for making these comparisons involves the following three steps:

1. CCM structure is represented as an image by treating coefficient matrix entries as pixel values in a digital image.
2. Automated feature engineering (through the use of deep learning techniques) is used to extract feature vectors from images.
3. The Euclidean distance between two feature vectors is treated as a measure of the similarity between the corresponding images. This distance is referred to as image-based structural similarity (ISS).

Lower ISS values imply a higher degree of similarity between the structure of two CCM images (identical CCM images will share an ISS value of zero).

CCM structure has previously been leveraged by a number of solution techniques in operations research (e.g., Dantzig-Wolfe decomposition). It has also been used to inform the selection of appropriate heuristic techniques. The ultimate goal of this research is to aid in the study of a given problem by highlighting solution approaches which were effective for structurally similar problems.

There are several projects, both completed and ongoing, involving the development and implementation of ICIP. Click on any of the project links below to see the corresponding results.