LPnetlib/lp_qap15

Netlib LP problem qap15: minimize c'*x, where Ax=b, lo<=x<=hi
Name lp_qap15
Group LPnetlib
Matrix ID 661
Num Rows 6,330
Num Cols 22,275
Nonzeros 94,950
Pattern Entries 94,950
Kind Linear Programming Problem
Symmetric No
Date
Author T. Johnson
Editor R. Bixby, M. Saltzman, T. Johnson
Structural Rank 6,330
Structural Rank Full true
Num Dmperm Blocks 1
Strongly Connect Components 1
Num Explicit Zeros 0
Pattern Symmetry 0%
Numeric Symmetry 0%
Cholesky Candidate no
Positive Definite no
Type integer
SVD Statistics
Matrix Norm 9.829069e+00
Minimum Singular Value 7.041975e-18
Condition Number 1.395783e+18
Rank 5,698
sprank(A)-rank(A) 632
Null Space Dimension 632
Full Numerical Rank? no
Download Singular Values MATLAB
Download MATLAB Rutherford Boeing Matrix Market
Notes
A Netlib LP problem, in lp/generators/qap.  For more information          
send email to netlib@ornl.gov with the message:                           
                                                                          
	 send index from lp                                                      
	 send readme from lp/data                                                
	 send readme from lp/generators/qap                                      
                                                                          
This copy of QAP15 was created by the QAP generator program,              
on an Sun UltraSparc, on May 15, 1997.                                    
                                                                          
The following are relevant excerpts from lp/data/readme (by David M. Gay):
                                                                          
The column and nonzero counts in the PROBLEM SUMMARY TABLE below exclude  
slack and surplus columns and the right-hand side vector, but include     
the cost row.  We have omitted other free rows and all but the first      
right-hand side vector, as noted below.  The byte count is for the        
MPS compressed file; it includes a newline character at the end of each   
line.  These files start with a blank initial line intended to prevent    
mail programs from discarding any of the data.  The BR column indicates   
whether a problem has bounds or ranges:  B stands for "has bounds", R     
for "has ranges".                                                         
                                                                          
The optimal value is from MINOS version 5.3 (of Sept. 1988)               
running on a VAX with default options.                                    
                                                                          
                       PROBLEM SUMMARY TABLE                              
                                                                          
Name       Rows   Cols   Nonzeros    Bytes  BR      Optimal Value         
QAP15      6331  22275   110700 (see NOTES)       1.0409940410E+03        
                                                                          
Problems QAP8, QAP12, and QAP15 are from a generator by Terri             
Johnson (communicated by a combination of Bob Bixby, Matt Saltzman, and   
Terri Johnson).                                                           
                                                                          
Source for Terri Johnson's generator and input data                       
for producing MPS files for QAP8, QAP12, and QAP15 appear in directory    
lp/generators/qap.                                                        
                                                                          
Added to Netlib on 12 April 1996.                                         
                                                                          
The following are relevant excerpts from lp/generators/qap/readme         
(by Terri Johnson):                                                       
                                                                          
        The Quadratic Assignment Problem (Problem QAP) is a specially-    
structured zero-one quadratic programming problem.  While having          
received considerable attention since its introduction into the           
literature over 30 years ago, and while many applications exist in        
various disciplines, this problem has resisted exact solution             
procedures.  Only for smaller-size problems can optimal solutions be      
obtained and verified.  The solution strategies for Problem QAP           
developed by Johnson (Ph.D.  dissertation, Clemson University, 1992)      
and Adams and Johnson (Improved Linear Programming-based Lower Bounds     
for the Quadratic Assignment Problem, DIMACS:  Quadratic Assignment       
and Related Problems, Vol. 16 (1994), 43-75) are based on a new,          
equivalent, mixed- integer linear reformulation, Problem LP.              
        The traditional , nonlinear formulation of Problem QAP has a      
quadratic objective function, 2m constraints and m^2 binary variables.    
The linearized version of concern, Problem LP, on the other hand, has     
2m^2(m-1) + m^2(m-1)^2/2 + 2m constraints, in addition to non-            
negativity restrictions on all the variables, and m^2 binary variables    
and m^2(m-1)^2 continuous variables.  The continuous relaxation of        
Problem LP, obtained by omitting the x binary restrictions, possesses     
a special block diagonal structure which readily lends itself to          
decomposition techniques.  However, the inherent degeneracy makes this    
a formidable program for problems as small in size as m=15 to 20.  A      
smaller reformulation, which reduces the number of constraints and        
variables each by m^2(m-1)^2/2, can be obtained via an appropriate        
substitution of variables, but such a substitution forfeits the           
problem structure.  It has been amply demonstrated that this              
formulation serves as a unifying and dominating entity with respect to    
the different linear reformulations of Problem QAP, as well as with       
respect to a variety of bounding procedures.  Consequently, the           
ability to quickly solve this linear formulation holds the promise of     
being able to solve larger-sized QAP's.                                   
        Provided here is Fortran source, newlp.f, for a program that      
generates MPS files for the linearized QAP with the substitution of       
variables.  Under the assumption that the test problem is symmetric,      
the generator reads the problem size, m, and an mxm matrix with the       
original distances in the upper half of the matrix and the original       
flows in the lower half of the matrix.  All diagonal entries are 0.       
Using this input, the generator program computes the objective            
function coefficients for the quadratic terms, and automatically          
computes the constraints.  The objective function is assumed to           
contain no linear terms since such values can be easily incorporated      
into the quadratic terms.                                                 
        Input files qap8.dat, qap12.dat, and qap15.dat cause the          
generator program to emit MPS files for well-known test problems of       
Nugent, C.E., T.E. Vollmann, and J. Ruml, An Experimental Comparison      
of Techniques for the Assignment of Facilities to Locations,              
Operations Research, Vol. 16, No. 1 (1968), 150-173, of sizes m=8, 12,    
and 15 for the linearization.                                             
                                                                          
                                                                          
PROBLEM:  M = 15		No. of Variables	No. of Constraints                     
                                                                          
	QAP				225			  30                                                        
	LP (with substitution)	      22275			6330                                
	Optimal value: 1.0409940410e+3                                           
                                                                          
For more information, please contact Terri Johnson at:                    
	johnsont@numen.elon.edu