Generating quadratic bilevel programming test problems

ABSTRACT

This paper describes a technique for generating sparse or dense quadratic bilevel programming problems with a selectable number of known global and local solutions. The technique described here does not require the solution of any subproblems. In addition, since most techniques for solving these problems begin by solving the corresponding relaxed quadratic program, the global solutions are constructed to be different than the global solution of this relaxed problem in a selectable number of upper- and lower-level variables. Finally, the problems that are generated satisfy the requirements imposed by all of the solution techniques known to the authors.

REFERENCES

• 1: BARD, J. 1983. Coordination of a multidivisional organization through two levels of management. Omega 11, 5 (Sept./Oct.), 457 468.
• 2: BEN-AYEr), O., BLAIR, C., AND BOYCE, D. 1988, Construction of a real world bilevel linear program of the highway design problem. Fac. Pap. 1464, College of Commerce and Business Administration, Univ. of Illinois at Urbana-Champaign, June.
• 3: BI, Z., CALAMAI, P., AND CONN, A. 1991. An exact penalty function approach for the nonlinear bllevel programming problem. Tech. Rep. 180-O-170591, Dept. of Systems Design Engineering, Univ. of Waterloo, Ontario, Canada.
• 4: DmICKX, Y., AND JENNEGREN, L. 1979. Systems Analysis by Multzlevel Methods' With Applicatm, s to Economics and Management Wiley, New York.
• 5: EDMUNDS, T., AND BARD, J. 1991. Algorithms for nonlinear bilevel mathematical programs. IEEE Trans. Syst. Marl Cybern. 21, I (Jan,/Feb.), 83 89.
• 6: Christodoulos A. Floudas , Panos M. Pardalos, A collection of test problems for constrained global optimization algorithms, Springer-Verlag New York, Inc., New York, NY, 1990
• 7: FORTUNY-AMAT, J., AND MCCARL, B. 1981. A representation and economic interpretation of a two-level programming problem. J. Oper. Res. Soc. 32, 9 (Sept.), 783-792.
• 8: GAUVIN, J., AND SAVARD, G. 1989. The steepest descent method for the nonlinear bilevel programming problem. Work. Pap., Ecole Polytechnique de Montreal, Montreal, Quebec, Canada.
• 9: B Kalantari , J B Rosen, Construction of large-scale global minimum concave quadratic test problems, Journal of Optimization Theory and Applications, v.48 n.2, p.303-313, Feb. 1986 [doi>10.1007/BF00940675]
• 10: KOLSTAD, C. 1985. A review of the literature on bi-level mathematical programming. Tech. Rep. LA-10284-MS, UC-32, Los Alamos National Laboratory, N.M., Oct.
• 11: Melanie L. Lenard , Michael Minkoff, Randomly Generated Test Problems for Positive Definite Quadratic Programming, ACM Transactions on Mathematical Software (TOMS), v.10 n.1, p.86-96, March 1984 [doi>10.1145/356068.356075]
• 12: MESANOVIC, M., MACKO, D., AND TAKAHARA, Y. 1970. Theory of Hierarchical, Multtlevel Systems. Academic Press, New York.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Certification and testing

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

General Terms:
Algorithms, Performance

Keywords:
bilevel programming, quadratic separable programs, test problems