tailieunhanh - An enumerative algorithm for non-linear multi-level integer programming problem

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. | Yugoslav Journal of Operations Research Volume 19 (2009) Number 2, 263-279 DOI: AN ENUMERATIVE ALGORITHM FOR NON-LINEAR MULTI-LEVEL INTEGER PROGRAMMING PROBLEM 1 Ritu NARANG Department of Mathematics, University of Delhi, India Department of Mathematics, Hans Raj College, University of Delhi, India Received: August 2007 / Accepted: September 2009 Abstract: 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. Keywords: Multilevel programming, indefinite quadratic programming, fractional programming, quasi-concave function, integer programming. 1. INTRODUCTION There are many planning and/or decision making situations that can be properly represented by a multi level programming model. The most important characteristic of multilevel programming problems is that a planner at a certain level of hierarchy may 1 Classification No.: Primary: 90C20, 90C10; Secondary: 90C32, 90C08 R., Narang, S. R., Arora / An Enumerative Algorithm 264 have his objective function and decision space determined partially by other levels. Mathematically, a multi level programming problem can be formulated as Max f1 ( X 1 ,, X k ) X1 Max f 2 ( X 1 ,, X k ) X2 : : Max f k ( X 1 ,, X k ) Xk (X1, X2, ., Xk) ∈ S where S is a convex feasible set and fj (X1, ., Xk), j = 1, 2,