Paul H. Calamai
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.
- BARD, J. 1983. Coordination of a multidivisional organization through two levels of management. Omega 11, 5 (Sept./Oct.), 457 468.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- DmICKX, Y., AND JENNEGREN, L. 1979. Systems Analysis by Multzlevel Methods' With Applicatm, s to Economics and Management Wiley, New York.Google Scholar
- EDMUNDS, T., AND BARD, J. 1991. Algorithms for nonlinear bilevel mathematical programs. IEEE Trans. Syst. Marl Cybern. 21, I (Jan,/Feb.), 83 89.Google Scholar
- FLOUDAS, C. A., AND PARDALOS, P. M. 1990, A Collection of Test Problems for Constrained Global Optimization Algorithms Lecture Notes zn Computer Science, vol. 455. Springer-Verlag, New York. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- KALANTARI, B., AND ROSEN, J.B. 1986. Construction of large-scale global minimum concave quadratic test problems. J. Optim. Theory Appl. 48, 2 (Feb.), 303 313. Google Scholar
- 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.Google Scholar
- LENARD, M., AND MINKOFF, M. 1984. Randomly generated test problems for positive definite quadratic programming. ACM Trans. Math. Softw. 10, I (Mar.), 86-96. Google Scholar
- MESANOVIC, M., MACKO, D., AND TAKAHARA, Y. 1970. Theory of Hierarchical, Multtlevel Systems. Academic Press, New York.Google Scholar
Index Terms
- Generating quadratic bilevel programming test problems
Recommendations
Algorithm 728: FORTRAN subroutines for generating quadratic bilevel programming test problems
This paper describes software for generating test problems for quadratic bilevel programming. The algorithm constructs problems with a number of favorable properties that can be selected and controlled by the user. The intention is to provide a set of ...
Global Optimization of Nonlinear Bilevel Programming Problems
A novel technique that addresses the solution of the general nonlinear bilevel programming problem to global optimality is presented. Global optimality is guaranteed for problems that involve twice differentiable nonlinear functions as long as the ...
On Bilevel programming and its impact in branching, cutting and complexity
CPAIOR'11: Proceedings of the 8th international conference on Integration of AI and OR techniques in constraint programming for combinatorial optimization problemsBilevel programming is a rich paradigm to express a variety of real-world applications including game theoretic and pricing ones. However, what we are interested in this talk is to discuss the bilevel nature of two of the most crucial ingredients of ...
Reviews
Timothy R. Hopkins
A source of valid test problems is an invaluable asset in testing the efficiency and scope of both existing and new algorithms. While test suites are available for a number of other areas of optimization, this work is the first attempt to address quadratic bilevel programming problems. The paper considers the transformation of simple two-variable, one-parameter quadratic bilevel programs into more general problems. It contains detailed analyses of both the simple problems and the transformations, along with a simple illustrative example. The proposed technique generates both sparse and dense test problems with a minimum of computational effort as well as allowing control over the condition of the resultant problem. The last section mentions that a FORTRAN 77 program implementing the method is available from the author. It is a great pity that such useful software was not also made available as a TOMS algorithm.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments