Construction of test problems in quadratic bivalent programming

ABSTRACT

A method of constructing test problems for constrained bivalent quadratic programming is presented. For any feasible integer point for a given domain, the method generates quadratic functions whose minimum over the given domain occurs at the selected point. Certain properties of unconstrained quadratic zero-one programs that determine the difficulty of the test problems are also discussed. In addition, a standardized random test problem generator for unconstrained quadratic zero-one programming is given.

REFERENCES

• 1: R D Babaev, The construction of test problems in integer-value programming with binary unknowns, USSR Computational Mathematics and Mathematical Physics, v.25 n.1-2, p.98-102, May 1986 [doi>10.1016/0041-5553(85)90048-5]
• 2: F Barahona, A solvable case of quadratic 0-1 programming, Discrete Applied Mathematics, v.13 n.1, p.23-26, Jan. 1986 [doi>10.1016/0166-218X(86)90065-X]
• 3: F. Barahona , M. Junger , G. Reinelt, Experiments in quadratic 0-1 programming, Mathematical Programming: Series A and B, v.44 n.2, p.127-137, 1989 [doi>10.1007/BF01587084]
• 4: CARTER, M W. The indefinite zero-one quadratic problem Discrete AppL Math. 7 (1984), 23-44
• 5: CHANG, M. G , AND SHEI~ARD$ON, F. An integer programming test problem generator In Lecture Notes in Economics and Mathematical Systems 199, J. M. Mulvey, Ed., 1982, pp. 146-160.
• 6: COOPER, M. A survey of methods for pure nonlinear integer programming. Manage. Sci. 3 (1980), 132-149.
• 7: GIANNESSI, F., Ai~ID NICCOLUCCI, F. Connections between nonlinear and integer programming problems. }n Symposia Mathematica, Vol. 19 (Inst. Nazionale Di Alta Math.). Academic Press, Orlando, Fla., 1976, pp. 161-176.
• 8: GULATI, V. P., GUPTA, S. K., AND MITAL, A.K. Unconstrained quadratic bivalent programming problems. European J. Oper. Res. 15 (1981), 121-125.
• 9: HAMMER, P. L., AND RUDEANU, S. Boolean Methods in Operations Research. Springer- Verlag, New York, 1969.
• 10: HAMMER, P. L., A~D SIMEONE, B. Order relations of variables in 0-1 programming. Annals Discrete Math. 31 (1987), 83-112.
• 11: HANSEN, P. Methods of nonlinear zero-one programming. Annals Discrete Math. 5 (1979), 53-70.
• 12: LEWIS, P., GOODMAN, A. S., AND MILLER, J. M. Pseudo-random number generator for the system/360. IBM Syst. J. 8, 2 (1969), 300-312.
• 13: MAY, J. H., AND SMITH, L.R. The definition and generation of geometrically random linear constraint sets. In Lecture Notes in Economics and Mathematical Systems 199, J. M Mulvey, Ed., 198'2, pp. 24-34.
• 14: Panos M. Pardalos, Generation of large-scale quadratic programs for use as global optimization test problems, ACM Transactions on Mathematical Software (TOMS), v.13 n.2, p.133-137, June 1987 [doi>10.1145/328512.328516]
• 15: P. M. Pardalos , J. H. Glick , J. B. Rosen, Global minimization of indefinite quadratic problems, Computing, v.39 n.4, p.281-291, Dec. 1987 [doi>10.1007/BF02239972]
• 16: P. M. Pardalos , G. P. Rodgers, Parallel branch and bound algorithms for quadratic zero-one programs on the hypercube architecture, Annals of Operations Research, v.22 n.1-4, p.271-292, Jan. 1990 [doi>10.1007/BF02023057]
• 17: PARDALOS, P. M. AND RODGERS, G. P. Parallel branch-and-bound algorithms for unconstrained zero-one programming. In Impacts of Recent Computer Advances on Operations Research, R. Sharda et al., Eds. North-Holland, New York, 1989, pp. 131-143.
• 18: Panos M. Pardalos , J. Ben Rosen, Constrained global optimization: algorithms and applications, Springer-Verlag New York, Inc., New York, NY, 1987
• 19: PICARD, J. C., AND QUEYRANNE, M. Selected applications of min cut in networks. INFOR 20, 4 (1982), 395-422.
• 20: RODGERS, G. P., AND PARDALOS, P. M. Computational aspects of a branch-and-bound algorithm for quadratic zero-one programming. Tech. Rep. CS-88-04, Dept. Computer Science, Pennsylvania State University, University Park, 1988.
• 21: RUBIN, A. A., AND HAMMER, P.L. Quadratic programming with zero-one variables. Revue Franc. d'Informat. Res. Operat. 4 (1970) 67-79.
• 22: SUNG, Y. Y., AND ROSEN, J.B. Global minimum test problem construction. Math. Progr. 24 (1982), 353-355.
• 23: WmLIAMS, A.C. Quadratic zero-one programming using the roof dual with computational results. RUTCOR Research Rep. 8-85, Rutgers University, 1985.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Nonlinear programming

General Terms:
Algorithms, Experimentation, Performance

Keywords:
global optimization, integer quadratic programming, test problems