An Inexact Restoration Package for Bilevel Programming Problems

Elvio A. Pilotta, Germán A. Torres

Facultad de Matemática, Astronomía y Física, Universidad Nacional de Córdoba, CIEM (CONICET), Córdoba, Argentina.

DOI: 10.4236/am.2012.330181                

Abstract

Bilevel programming problems are a class of optimization problems with hierarchical structure where one of the con-straints is also an optimization problem. Inexact restoration methods were introduced for solving nonlinear programming problems a few years ago. They generate a sequence of, generally, infeasible iterates with intermediate iterations that consist of inexactly restored points. In this paper we present a software environment for solving bilevel program-ming problems using an inexact restoration technique without replacing the lower level problem by its KKT optimality conditions. With this strategy we maintain the minimization structure of the lower level problem and avoid spurious solutions. The environment is a user-friendly set of Fortran 90 modules which is easily and highly configurable. It is prepared to use two well-tested minimization solvers and different formulations in one of the minimization subproblems. We validate our implementation using a set of test problems from the literature, comparing different formulations and the use of the minimization solvers.

Keywords

Bilevel Programming Problems; INEXACT Restoration Methods; Algorithms

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	H. V. Stackelberg, “Marktform and Gleichgewicht,” Springer-Verlag, Berlin, 1934.
[2]	J. F. Bard, “Practical Bilevel Optimization: Algorithms and Applications,” Kluwer Academic Publishers, Dordrecht, 1998.
[3]	L. N. Vicente, “Bilevel Programming: Introduction, History, and Overview,” In: Encyclopedia of Optimization, Kluwer Academic Publishers, Dordrecht, 2001, pp. 24-31. doi:10.1007/0-306-48332-7_38
[4]	S. Dempe, “Foundations of Bilevel Programming,” Kluwer Academic Publishers, Dordrecht, 2002.
[5]	S. Dempe, “A Necessary and a Sufficient Optimality Condition for Bilevel Programming Problems,” Optimization, Vol. 25, No. 4, 1992, pp. 341-354. doi:10.1080/02331939208843831
[6]	R. Andreani, S. L. C. Castro, J. L. Chela, A. Friedlander and S. A. Santos, “An Inexact-Restoration Method for Nonlinear Bilevel Programming Problems,” Computational Optimization and Applications, Vol. 43, No. 3, 2009, pp. 307-328. doi:10.1007/s10589-007-9147-4
[7]	S. Dempe, “Annottated Bibliography on Bilevel Programming and Mathematical Problems with Equilibrium Constraints,” Optimization, No. 52. No. 3, 2003, pp. 333-359. doi:10.1080/0233193031000149894
[8]	S. Dempe, “A Simple Algorithm for the Linear Bilevel Programming Problem,” Optimization, No. 18, No. 3, 1987, pp. 373-385. doi:10.1080/02331938708843247
[9]	J. E. Falk and J. Liu, “Annotated Bibliography on Bilevel Programming and Mathematical Programs with Equilibrium Constraints,” Central European Journal of Operations Research, Vol. 52, No. 2, 1993, pp. 101-117.
[10]	L. Brotcorne, M. Labbè, P. Marcotte and G. Savard, “A Bilevel Model and Solution Algorithm for a Freight Tariff Setting Problem,” Transportation Science, Vol. 34, No. 3, 2000, pp. 289-302. doi:10.1287/trsc.34.3.289.12299
[11]	M. G. Nicholls, “The Application of Nonlinear Bilevel Programming to the Aluminium Industry,” Journal of Global Optimization, Vol. 8, No. 3, 1996, pp. 245-261. doi:10.1007/BF00121268
[12]	J. Herskovits, A. Leontiev, G. Dias and G. Santos, “Contact Shape Optimization: A Bilevel Programming Approach,” Structural and Multidisciplinary Optimization, Vol. 20, No. 3, 2000, pp. 214-221.
[13]	P. Marcotte and G. Savard, “Bilevel Programming: Applications,” In: Encyclopedia of Optimization, Kluwer Academic Publishers, Dordrecht, 2001. doi:10.1007/0-306-48332-7_33
[14]	J. M. Martínez, “Two-Phase Model Algorithm with Global Convergence for Nonlinear Programming,” Journal of Optimization Theory and Applications, Vol. 96, No. 2, 1998, pp. 397-436. doi:10.1023/A:1022626332710
[15]	J. M. Martínez and E. A. Pilotta, “Inexact Restoration Algorithm for Constrained Optimization,” Journal of Optimization Theory and Applications, Vol. 104, No. 1, 2000, pp. 135-163. doi:10.1023/A:1004632923654
[16]	J. M. Martínez and E. A. Pilotta, “Inexact Restoration Methods for Nonlinear Programming: Advances and Perspectives,” In: L. Q. Qi, K. Teo and X. Q. Yang, Eds., Optimization and Control with Applications, Applied Optimization Series, Chapter 12, Springer, Netherlands, 2005, pp. 271-292.
[17]	E. G. Birgin and J. M. Martínez, “Local Convergence of an Inexact-Restoration Method and Numerical Experiments,” Journal of Optimization Theory and Applications, Vol. 127, No. 2, 2005, pp. 229-247. doi:10.1007/s10957-005-6537-6
[18]	B. A. Murtagh and M. A. Saunders, “Large-Scale Linearly Constrained Optimization,” Mathematical Programming, Vol. 14, No. 1, 1978, pp. 41-72. doi:10.1007/BF01588950
[19]	W. Murray, P. E. Gill and M. A. Saunders, “SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization,” SIAM Journal on Optimization, Vol. 12, No. 4, 2002, pp. 979-1006.
[20]	E. G. Birgin and J. M. Martínez, “Large-Scale Active-Set Box-Constrained Optimization Method with Spectral Projected Gradients,” Computational Optimization and Applications, Vol. 23, No. 1, 2002, pp. 101-125. doi:10.1023/A:1019928808826
[21]	S. R. Hejazi, A. Memariani, G. Jahanshahloo and M. M. Sepehri, “Linear Bilevel Programming Solution by Genetic Algorithm,” Computers & Operations Research, Vol. 29, No. 13, 2002, pp. 1913-1925. doi:10.1016/S0305-0548(01)00066-1
[22]	GAMS, http://www.gams.com/
[23]	V. Visweswaran, C. A. Floudas, M. G. Ierapetritou and E. N. Pistikopoulos, “State of the Art in Global Optimization: Computational Methods and Applications,” Kluwer Academic Publishers, Dordrecht, 1996.
[24]	B. Colson, P. Marcotte and G. Savard, “A Trust-Region Method for Nonlinear Bilevel Programming: Algorithm and Computational Experience,” Computational Optimization and Applications, Vol. 30, No. 3, 2005, pp. 211-227. doi:10.1007/s10589-005-4612-4
[25]	CPLEX http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/
[26]	P. Spellucci, “An SQP Method for General Nonlinear Programs Using Only Equality Constrained Subproblems,” Mathematical Programming, Vol. 82, No. 3, 1998, pp. 413-448. doi:10.1007/BF01580078
[27]	E. Karas, E. Pilotta and A. Ribeiro, “Numerical Comparison of Merit Function with Filter Criterion in Inexact Restoration Algorithms Using Hard-Spheres Problems,” Computational Optimization and Applications, Vol. 44, No. 3, 2009, pp. 427-441. doi:10.1007/s10589-007-9162-5
[28]	C. A. Floudas, P. M. Pardalos, C. S. Adjiman, W. R. Esposito, Z. Gumus, S. T. Harding, J. L. Klepeis, C. A. Meyer and C. A. Schweiger, “Handbook of Test Problems for Local and Global Optimization,” Kluwer Academic Publishers, Dordrecht, 1999. doi:10.1007/BF01585928
[29]	J. E. Falk and J. Liu, “On Bilevel Programming, Part I: General Nonlinear Cases,” Mathematical Programming, Vol. 70, No. 1, 1995, pp. 47-72.
[30]	Z. H. Gumus and C. A. Floudas, “Global Optimization of Nonlinear Bilevel Programming Problems,” Journal of Global Optimization, Vol. 20, No. 1, 2001, pp. 1-31. doi:10.1023/A:1011268113791
[31]	K. Shimizu, Y. Ishizuka, and J. F. Bard, “Nondifferentiable and Two-Level Mathematical Programming,” Kluwer Academic Publishers, 1997. doi:10.1007/978-1-4615-6305-1