International Journal of Innovative Research in Science, Engineering and Technology

International Journal of Innovative Research in Science, Engineering and Technology

Menu

ISSN ONLINE(2319-8753)PRINT(2347-6710)

All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

A PROCEDURE FOR SOLVING INTEGER BILEVEL LINEAR PROGRAMMING PROBLEMS

A.Y. Adhami1, and Quazzafi Rabbani2
Assistant Professor, Department of Mathematics, Integral University, Lucknow, India1,2
Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Science, Engineering and Technology

International Journal of Innovative Research in Science, Engineering and Technology

Abstract

This paper is an extension of the K th-best approach [4] for solving bilevel linear programming problems with integer variables. NAZ cut [2] and A-T cut [3] are added to reach the integer optimum. An example is given to show the efficiency of the proposed algorithm.

Keywords
A-T cut, bilevel linear integer programming, K th-best approach, NAZ cut.

INTRODUCTION
Bilevel programming has been proposed for dealing with decision processes involving two decision makers with a hierarchical structure. A bilevel programming problem (BLPP) consists of two levels, namely, the first level and the second level. The first level decision maker is called the leader and the second is called the follower. The follower executes its policies after and in view of, the decisions of higher level decision maker i.e. leader. In terms of applications, bilevel programming has been used in many domains, e.g. to design optimization problems in process system engineering [6], design of transportation network [11], agricultural planning [9], management of multi-divisional firms [14]. Many researchers have designed algorithms for the solution of the BLPP [1, 4, 5, 8, 10]. However, there has been very little attention in the literature on both the solution and the application of bilevel problems involving discrete decisions. This is mainly because these problems pose major algorithmic challenges in the development of effective solution strategies. For the solution of the purely integer linear BLPP, a branch and bound type of enumerative solution algorithm has been developed by Moore and Bard [12]. Cutting plane and parametric solution approaches have been developed by Dempe [7]. Saharidis and Ierapetritou [15] gave an algorithm for the resolution of mixed integer BLPP based on Benders decomposition method. In this paper we focus on the integer linear bilevel programming problem, in which all involved functions are linear. The aim of this paper is to present an extended K th-best approach for finding the integer solution to a bilevel programming problem by introducing A-T cut to the reduced feasible region obtained after using NAZ cut.

II. DESCRIPTION OF NAZ CUT AND A-T CUT FOR INTEGER LINEAR PROGRAMMING PROBLEMS
image
image

III. THE PROCEDURE
Using the common notation in bilevel programming, the integer linear bilevel programming ILBP problem can be written as follows:
image
image
image

IV. NUMERICAL EXAMPLE
image
image

V CONCLUSION
We have extended the Kth-best algorithm for solving linear bilevel programming problems with the help of NAZ cut for integer programming along with the A-T cut. This algorithm gives us the integer solution for bilevel programming problems with much computational ease.

References
  1. J.F. Bard, “An Algorithm for Solving the General Bilevel Programming Probem”. Mathematics of Operations Research. Vol. 8, No.2, pp. 260-272, 1983.
  2. A. Bari, and Q. S. Ahmad, “NAZ cut for Integer Programming”. Pure and Applied Mathematika Sciences. Vol LVII, No.1-2, 87-94, 2003.
  3. A. Bari, and T. Alam, “Search for Integer Optimum after Adding NAZ cut”. Pure and Applied Mathematika Sciences. Vol. LXII, No. 1-2, pp. 77-83, 2005.
  4. W. F. Bialas, and M. H. Karwan, “Two Level Linear Programming”, Management Science, Vol. 30, No. 8, pp.1004-1020, 1984.
  5. M Campelo and S. Scheimberg, “A Simplex Approach for Finding Local Solutions of a Linear Bilevel Program by Equilibrium Points” Annals of Operations Research. Vol. 138, pp. 144-157, 2005.
  6. P. A. Clark and A.W.Westerberg, “Bilevel Programming for Steady-State Chemical Process Design – I. Fundamentals and Algorithms”. Comput. Chem. Eng. Vol. 14, No. 1, pp. 87-97 , 1990.
  7. S. Dempe, “DiscreteBilevelOptimizationProblems”.http;//www.mathe.tufreiberg.de/ dempe, TU Chemnitz.
  8. N.P. Faísca, V. Dua, B. Rustem, P.M. Saraiva, E.N. Pistikopoulos, “Parametric Global Optimization for Bilevel Programming”. Journal of Global Optimization. Vol. 38, pp. 609-623, 2007.
  9. J. Fortuny-Amat, B. McCarl, “A Representation and Economic Interpretation of a Two-Level Programming Problem”. Journal of Operations Research Society. Vol. 32, No. 9, pp. 783-792, 1981.
  10. J. Judice, and A. Faustino, “A Sequential LCP method for Bilevel Linear Programming”. Annals of Operations Research. Vol. 34, pp. 89-106, 1992.
  11. L.J. LeBlanc, and D.E. Boyce, “A Bilevel Programming Algorithm for Exact Solution of Network Design Problem with User-Optimal Flows”. Trans. Res.-Part B, Vol. 20, pp.259-265, 1985.
  12. J.T. Moore, and J.F. Bard. “The Mixed Integer Linear Bilevel Programming Problem”. Operations Research. Vol. 38, pp. 911-921, 1990.
    13. Q. Rabbani, and A.Y. Adhami, “A Note on NAZ cut for Integer Progrmming” Pure and Applied Mathimatika Sciences, Vol. LXVIII, No. 1-2, pp. 75- 77, 2008
  13. J. Ryu, V. Dua, E.N. Pistikopoulos, “A Bilevel Programming Framework for Enterprise-Wide Process Networks under uncertainty”. Comput. Chem. Eng. Vol. 28, pp. 1121-1129, 2004.
  14. G.K. Saharidis, and M. G. Ierapetritou, “Resolution Method for Mixed Integer Bilevel Linear Problems Based on Decomposition Technique”. J. Glob. Optim. 2008.