[Coin-discuss] Structural comparison of MPS files?

[Michael Hennebry]

On Wed, 6 Apr 2016, acw at ascent.com wrote:

> I could use a tool that takes two MPS files and compares them
> structurally. Specifically, it should not be "mazed" by mere name and
> order changes of rows and columns -- it should be able to recognize two
> isomorphic problems, and it would be wonderful if it could recognize
> only-mostly-isomorphic problems as well. It should give name changes and
> structural differences.

The problem is roughly equivalent to discovering
whether two matrices are isomorphic.

An important part of any such technique will be discovering
whether any two rows or columns are permutations of each others.
Sort the coefficients and compare the results.

A technique that will discover that many pairs of matrices are not isomorphic:
Sort each row of each matrix.
Lexigraphically sort the rows of each matrix.
If the new matrices are not the same,
the original matrices were not isomorphic.
If the matter is not already decided, do the same with columns.

For an exact solution, here is a brute force technique:
Call the matrices P and Q.
Two sets of assignment constraints, one for the rows and one for the columns.
x[r,s] = 1 iff P[r,*] matches Q[s,*]
y[c,d] = 1 iff P[*,c] matches Q[*,d]
SUM x[r,s] = 1   all s
  r
SUM y[c,d] = 1   all d
  c
SUM x[r,s] = 1   all r
  s
SUM y[c,d] = 1   all c
  d

x[r,s] + y[c,d] <= 1  for all r,s,c,d such that P[r,c] != Q[s,d]

Solve the binary feasibility problem.

The brutality can be reduced somewhat:
Partition the rows into equivalence classes:
Two rows are in the same equivalence class
iff one is a permutation of the other.
One can do better with the columns:
Temporarily replace each matrix entry in each matrix with (entry, class),
where class is the class of the row.
Partition the columns into equivalence classes.
Two columns are equivalent iff one is a permutation of the others.
Temporarily replace each matrix entry with (entry, class),
where class is the class of the entry's column.
Rinse and repeat until no progress is made.

x[r,s] is 0 if P[r,*] and Q[s,*] are in distinct classes.
y[c,d] is 0 if P[*,c] and Q[*,d] are in distinct classes.

-- 
Michael   hennebry at web.cs.ndsu.NoDak.edu
"Sorry but your password must contain an uppercase letter, a number,
a haiku, a gang sign, a heiroglyph, and the blood of a virgin."
                                                              --  someeecards