An enumerative algorithm for non-linear multi-level integer programming problem
DOI:
https://doi.org/10.2298/YJOR0902263NKeywords:
multilevel programming, indefinite quadratic programming, fractional programming, quasi-concave function, integer programmingAbstract
In this paper a multilevel programming problem, that is, three level programming problem is considered. It involves three optimization problems where the constraint region of the first level problem is implicitly determined by two other optimization problems. The objective function of the first level is indefinite quadratic, the second one is linear and the third one is linear fractional. The feasible region is a convex polyhedron. Considering the relationship between feasible solutions to the problem and bases of the coefficient sub-matrix associated to the variables of the third level, an enumerative algorithm is proposed, which finds an optimum solution to the given problem. It is illustrated with the help of an example. .References
Anandalingam, C., “A mathematical programming model of decentralized multi-level systems”, Journal of Operational Research Society, 39 (6) (1988) 1021-1033.
Al-Khayyal, F.A., Horst, R., and Pardalos, P., “Global optimization of concave functions subject to quadratic constraints: An application in non-linear bilevel programming”, Annals of Operations Research, 34 (1992) 125-147.
Cabot, A., and Francis, R.L., “Solving certain non-convex quadratic minimization problems by ranking extreme points”, Operations Research, 18 (1970) 82-86.
Calvete, H.I., and Gale, C., “On the quasi-concave bilevel programming problem”, Journal of Optimization Theory and Applications, 98 (3) (1998) 613-622.
Calvete, H.I., Gale, C., and Mateo, P., “A new approach for solving linear bilevel problems using genetic algorithms”, European Journal of Operational Research, 188 (1) (2008) 14-28.
Candler, W., and Norton, R., “Multilevel programming”, Technical report 20, World Bank Development Research Center, Washington, D.C., 1977.
Falk, J.E., and Soland, R.M., “An algorithm for solving separable non-convex programming problems”, Management Science, 15 (1969) 550-569.
Konno, H., “Maximization of convex quadratic function under linear constraints”, Mathematical Programming, 11 (1976) 117-127.
Konno, H., and Kuno, T., “Linear multiplicative programming”, Mathematical Programming, 56 (1992) 51-64.
Majthey, A., and Whinston, A., “Quasiconcave minimization subject to linear constraints”, Discrete Mathematics, 1 (1974) 35-39.
Mathur, K., and Puri, M.C., “On bilevel fractional programming”, Optimization, 35 (1995) 215-226.
Murty, K.G., “Solving the fixed charge problems by ranking the extreme points”, Operations Research, 16 (1969) 268-279.
Faisca, P., Nuno, Dua, Vivek, Rustem, Berc, Saraiva, M., Pedro, Pistikopoulos, N., and Efstratios, “Parametric global optimization for bilevel programming”, Journal of Global Optimization, 38 (2007) 609-623.
Yi, P., Cheng, G., and Jiang, L., “A sequential approximate programming strategy for performance measure-based probabilistic structural design optimization”, Structural Safety, 30 (2) (2008) 91-109.
Rosen, J.B., “Global minimization of a linearly constrained concave function by partition of feasible domain”, Mathematics of Operations Research, 8 (1983) 215-230.
Sun, Dazhi, Benekohal, Rahim, F.W., Waller, and Travis, S., “Bilevel programming formulation and heuristic solution approach for dynamic traffic signals optimization”, Computer-Aided Civil and Infrastructure Engineering, 21 (5) (2006) 321-333.
Thoi, N.V., and Tuy, H., “Convergent algorithms for minimizing a concave function”, Mathematics of Operations Research, 5 (1980) 556-566.
Vicente, L., and Calamai, P.H., “Bilevel and multilevel programming: A bibliography review”, Journal of Global Optimization, 5 (1994) 291-306.
Zwart, P.B., “Global maximization of a convex function with linear inequality constraints”, Operations Research, 22 (1974) 602-609.
Downloads
Published
Issue
Section
License
Copyright (c) 2009 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
