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
Al-Khayyal, F.A., Horst, R., Pardalos, P. (1992) Global optimization of concave functions subject to quadratic constraints: An application in nonlinear bilevel programming. Annals of Operations Research, 34(1): 125
Anandalingam, G. (1988) A mathematical programming model of decentralized multi-level systems. Journal of the Operational Research Society, 39(11): 1021
Cabot, A., Francis, R.L. (1970) Solving certain non-convex quadratic minimization problems by ranking extreme points. Operations Research, 18(1): 82
Calvete, H.I., Gale, C. (1998) On the quasi-concave bilevel programming problem. Journal of Optimization Theory and Applications, 98(3): 613
Calvete, H.I., Gale, C., Mateo, P. (2008) A new approach for solving linear bilevel problems using genetic algorithms. European Journal of Operational Research, 188(1): 14
Candler, W., Norton, R. (1977) Multilevel programming. Washington, DC: World Bank Development Research Center, Technical report, 20
Faisca, N.P., Dua, V., Rustem, B., Saraiva, P.M., Efstratios, P.N. (2007) Parametric global optimisation for bilevel programming. Journal of Global Optimization, 38(4): 609
Falk, J.E., Soland, R.M. (1969) An Algorithm for Separable Nonconvex Programming Problems. Management Science, 15(9): 550
Konno, H., Kuno, T. (1992) Linear multiplicative programming. Mathematical Programming, 56(1-3): 51
Konno, H. (1976) Maximization of A convex quadratic function under linear constraints. Mathematical Programming, 11(1): 117
Majthey, A., Whinston, A. (1974) Quasi-concave minimization subject to linear constraints. Discrete Mathematics, 9(1): 35
Mathur, K., Puri, M.C. (1995) On bilevel fractional programming. Optimization, 35(3): 215
Murty, K.G. (1968) Solving the fixed-charge problem by ranking the extreme points. Operations Research, 16, 268-279
Rosen, J.B. (1983) Global minimization of a linearly constrained concave function by partition of feasible domain. Mathematics of Operations Research, 8(2): 215
Sun, D., Benekohal, R., Waller, F., Travis, S. (2006) Bi-level Programming Formulation and Heuristic Solution Approach for Dynamic Traffic Signal Optimization. Computer-Aided Civil and Infrastructure Engineering, 21(5): 321
Thoi, N.V., Tuy, H. (1980) Convergent algorithms for minimizing a concave function. Mathematics of Operations Research, 5(4): 556
Vicente, L., Calamai, P.H. (1994) Bilevel and multilevel programming: A bibliography review. Journal of Global Optimization, 5(3): 291
Yi, P., Cheng, G., Jiang, L. (2008) A sequential approximate programming strategy for performance-measure-based probabilistic structural design optimization. Structural Safety, 30(2): 91
Zwart, P.B. (1974) Global maximization of a convex function with linear inequality constraints. Operations Research, 22(3): 602
Downloads
Published
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
