The Pseudo-Boolean Optimization Website

 Benchmark Problems

Home Up

Beasley BHT GKA F1 F2 G1 G2

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 (qij);
c- - The lower bound of the diagonal coefficients (qii);
c+ - The upper bound of the diagonal coefficients (qii);
q- - The lower bound of the off-diagonal coefficients (qij);
q+ - The upper bound of the off-diagonal coefficients (qij);
s - A seed to initialize the random number generator;
qii~discrete uniform(c-,c+),i=1,...,n;
qij=qji~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.

Copyright © 2003 RUTCOR.
For problems or questions regarding the PBO website contact pbo@rutcor.rutgers.edu.
Last updated: May 20, 2004.