**Matrix: Mittelmann/nug08-3rd**

Description: LP lower bounds for quadratic assignment problems

(bipartite graph drawing) |

Matrix properties | |

number of rows | 19,728 |

number of columns | 29,856 |

nonzeros | 148,416 |

structural full rank? | yes |

structural rank | 19,728 |

# of blocks from dmperm | 1 |

# strongly connected comp. | 1 |

explicit zero entries | 0 |

nonzero pattern symmetry | 0% |

numeric value symmetry | 0% |

type | integer |

structure | rectangular |

Cholesky candidate? | no |

positive definite? | no |

author | S. Karisch, F. Rendl |

editor | H. Mittelmann |

date | 1995 |

kind | linear programming problem |

2D/3D problem? | no |

Additional fields | size and type |

b | full 19728-by-1 |

c | full 29856-by-1 |

lo | full 29856-by-1 |

hi | full 29856-by-1 |

z0 | full 1-by-1 |

Notes:

Hans Mittelmann test set, http://plato.asu.edu/ftp/lptestset minimize c'*x, subject to A*x=b and lo <= x <= hi NUG: computing LP lower bounds for quadratic assignment problems. see S.E. KARISCH and F. RENDL. Lower bounds for the quadratic assignment problem via triangle decompositions. Mathematical Programming, 71(2):137-152, 1995. K.G. Ramakrishnan, M.G.C. Resende, B. Ramachandran, and J.F. Pekny, "Tight QAP bounds via linear programming," Combinatorial and Global Optimization, P.M. Pardalos, A. Migdalas, and R.E. Burkard, eds., World Scientific Publishing Co., Singapore, pp. 297-303, 2002.

Ordering statistics: | result |

nnz(V) for QR, upper bound nnz(L) for LU, with COLAMD | 184,473,912 |

nnz(R) for QR, upper bound nnz(U) for LU, with COLAMD | 114,635,182 |

SVD-based statistics: | |

norm(A) | 8.11519 |

min(svd(A)) | 4.76129e-118 |

cond(A) | 1.70441e+118 |

rank(A) | 18,270 |

sprank(A)-rank(A) | 1,458 |

null space dimension | 1,458 |

full numerical rank? | no |

singular value gap | 2.98861e+13 |

singular values (MAT file): | click here |

SVD method used: | s = svd (full (R)) ; where [~,R,E] = spqr (A') with droptol of zero |

status: | ok |

For a description of the statistics displayed above, click here.

*Maintained by Tim Davis, last updated 12-Mar-2014.Matrix pictures by cspy, a MATLAB function in the CSparse package.
Matrix graphs by Yifan Hu, AT&T Labs Visualization Group.
*