| |
Pardalos and Rodgers ([1]) have proposed a test problem generator for
*Unconstrained Quadratic Binary Programming *(UQBP). Their routine generates symmetric integer matrices and has several parameters to control the characteristics of the problem,
namely:
| *n* - The number of variables ; |
| *d* - The density, i.e. the probability that a nonzero will occur for any
off-diagonal coefficient (*q*_{ij}); |
| *c*^{-} - The lower bound of the
diagonal coefficients (*q*_{i}_{i}); |
| *c*^{+} - The upper bound of the
diagonal coefficients (*q*_{i}_{i}); |
| *q*^{-} - The lower bound of the
off-diagonal coefficients (*q*_{ij}); |
| *q*^{+} - The upper bound of the
off-diagonal coefficients (*q*_{ij}); |
| *s* - A seed to initialize the random number
generator; |
| *q*_{ii}~discrete uniform(c^{-},c^{+}),i=1,...,n; |
| *q*_{ij}=q_{ji}~discrete uniform(q^{-},q^{+}),1£i<j£n. |
The *expected degree* of each UBQP instance is the
expected number of quadratic nonzeros per variable. Therefore, the set of
Pardalos problems have a fixed expected degree, i.e. (*n*-1)*d*.
[1] - P. Pardalos and G. P. Rodgers, (1990), ''Computational aspects of a branch and bound algorithm for quadratic 0-1 programming'',
*Computing* ** 45** 131-144. |