Finding the Beauty in Optimization Models - Visualizing MPS data sets

5

In 2013, Rick Wicklin blogged about visualizing matrices as heat maps using SAS/IML. That post reminded me that we had done a similar thing for the coefficient matrices in our optimization problems. In particular, we have developed some SAS macros to visualize the input data sets for the OPTLP (linear optimization) and OPTMILP (mixed integer linear optimization) procedures. The results are stunning pictures, revealing a lot of inner structure.

Practical optimization problems almost always have a very marked structure. Understanding and exploiting this structure is often critical to being able to solve the problem. Visualization is a key step toward this.

A couple of years ago, my colleague Philipp Christophel wrote some macros to visualize SAS MPS data sets. We then ran these on several hundred data sets and generated two sets of output images: 1024x768 PNG for casual viewing, and full resolution SVG to be able to dig deeper. Some of these MPS data sets are huge (the largest one is about 35GB), so the image creation took some time. Additionally, the largest SVG image is more than 7GB: that is a true test for any SVG writer/viewer.

Here is a gallery of the nicest ones with some explanation of where they come from. Each row corresponds to a constraint and each column to a decision variable. All of our instances are sparse, where only a small fraction of the coefficients are nonzero. In the plots below only the nonzero coefficients are colored.

First a couple of instances where each nonzero coefficient is +1:

A set packing/covering instance coming from the Italian Railway company. From a distance it looks like a railway timetable. This is part of the MIPLIB2010 set.
fast0507

Next is a fully symmetric instance. All the variables are equivalent to each other. MILP solvers have to exploit this structure to be able to solve this instance in a reasonable time.
cod105

How to place a maximum number of queens on a 30x30 chessboard so that each queen attacks at most one other queen. Model from MIPLIB2010.
queens_30_r

Next here are a couple of scheduling instances. First an ACC basketball scheduling instance, again from MIPLIB2010.
acc_tight5

A workforce scheduling/assignment problem contributed by Gergely Bathó. You can see the nice block structure: that is a good candidate for decomposition: most constraints use only a few decision variables, and there are a few linking constraints (top and bottom) that impose some global restriction on the variables.
scheduling1

A fairly complicated model of scheduling ocean freight shipments. Again, you can clearly see the different kinds of variables and constraints and how the problem could be decomposed.
shipping

A production optimization model from a major oil company:
production

Finally, another instance with a very clearly decomposable structure, made up of a lot of tiny blocks.
neos_799838

Would you like to see any of these on your wall? Just leave a comment below and we can get you a high resolution image for printing. Also, feel free to share any tips you have on how we could make the plots nicer.

Share

About Author

Imre Pólik

Principal Operations Research Specialist

Imre Pólik is an Optimization Solver Developer for SAS/OR, working on the linear and mixed-integer optimization solvers. He earned his M.S. in Mathematics from Eötvös University in Budapest, Hungary, and his Ph.D. in Mathematics from McMaster University, Hamilton, Ontario, Canada. He has worked for SAS since 2010, following a couple of years as a visiting assistant professor at Lehigh University.

5 Comments

  1. Daymond Ling on

    Wow! Phenomenally interesting visualization. You must've something really creative to order the rows & columns for the visual to work, random ordering of constraint rows and decision variable columns would probably not reveal the structure. Great work.

    • Imre Pólik

      Thanks! Actually, rows and columns are in their original order. Similar variables and constraints tend to come in batches. You can see with some problems that reordering them would create an even nicer picture.

Leave A Reply

Back to Top