A Problem based on Lagrange Relaxation Approach & Solving Optimization on Bi-level Model Programming Problem

Abstract

In this paper, a salutation method based on Lagrange relaxation for discrete-continuous bi-level problems, with binary variables in the leading problem, considering the optimistic approach in bi-level programming. Linearized taking advantage of the structure of the leading problem, an algorithm is solving two-dimensional bi-level linear programming problems, classification of constrains, algorithm removes all redundant constraints, cycling and solution of problem.

Introduction

I. INTRODUCTION

Optimization is the process of making something as good as possible. In operation research optimization problem can be defined as the problem of finding the best solution of better than previously known the best solution among a set of feasible solution by trying different variations of the input [1]. Optimization problems can be categorized as either continuous discrete, based on the nature of the variables in the optimization function. The original formulation for Bi-level programming problem appeared in 1973, in a paper authored by J. Bracken and J. McGill [2], W. Candler and R. Norton [3]. It used the designation bi-level or multilevel programming. It was not until the early eighties that these problems started receiving the attention they deserve [4] [5] [6] [7]. Several authors studies bi-level programming problem intensively and contributed to its proliferation in the mathematical programming community. In general, a bi-level programming problem is difficult to solve [8], proved that even the simplest case, as the linear bi-level problem. Since 1980, a significant efforts have been devoted to understanding the fundamental concepts associated with bi-level programming various version of the linear bi-level programming problem are present by [9] [10] [11] [12]. At the same time, various algorithms have been proposed for solving these problems. Techniques inherent of extreme point algorithms and has been largely applied to the linear bi-level programming problems because for this problem, for a solution, then there is at least one global minimizer that is an extreme point [13]. In many bi-level programming problem, a subset of variable is restricted to taking discrete values. These characteristics [14] [15] [16] proposed branch and bound algorithms for mixed and binary integers [17] developed a branch and bound algorithm to solve binary non-linear mixed integer problem. It is pointed out [18] that the branch and bound methods require linear or non-linear convex functions at the lower level of the bi-level problem to be functional. Proposed fundamental properties to solution in bi-level linear programs with binary variables. Its penalty function method to solve discrete bi-level problems [19]. A reformulation and linearization algorithm for the whole bi-level mixed-integer general problem with continuous variables in the follower using the representation of its convex Hull [20]. Two others classes of Algorithms using multi parametric programming to solve bi-level integer problems with the integer variable controlled by first level [21]. An algorithms based on the same strategy for bi-level mixed integer problems where the follower solves an integer problem [22]. A survey on the linear bi-level programming problem has been written by O. Ben–Ayed [23]. The complexity of the problem has been addressed by a number of authors [24] [25] [26]. It has been proved that even the linear bi-level programming problem [27] [28]. An algorithm for the global optimization of bi-level mixed-integer nonlinear problems consisting of generating a convergent lower bounded and an optimal upper bound [29]. An exact algorithm for the linear mixed-integer bi-level problem with some simplification. Considered integer bi-level problems with the leader objective function being linear-fractional and linear the follower, it proposed an iterative algorithm of cut generation to solve the problem [24]. Using decomposition techniques, an algorithm based on benders decomposition to solve the linear mixed integer binary problem, with the method, the target value bounded, are used to transform the problem into problems of one level [25]. Based on the use of benders decomposition with a continuous sub problems [26, 30].

A solution method for discrete continuous bi-level problem based on Lagrange relaxation is presented. The nonlinear problem can be linearized by taking advantage of the structure of the binary variables of the leader problem. An attempt has been made a develop a method in which contractions are analysed, and used for solved two-dimensional linear bi-level programming problems our proposal allows us to find a global optimal through a decomposition technique, taking advantage of some characteristics of the problems involved. This paper is organized as follow: the definition and formulation of the discrete continuous bi-level problems. 

V. FUTURE WORK & SCOPE

The approach will be used without considering the single level reformulation of the bi-level problem and the consideration of more than one objective in the leaser function. The method can be used for problems involving cooperative decision-making at two level e.g. allocation of resources at minimum cost considering maximisation of the level of service, location of unwanted facilities, among others.

Conclusion

The proposed method is based on the analysis constraints. The traditionally used of finding optimum such as interior point method or simplex method in which search is made by moving along the boundary of the feasible region the properties of constraints there is a possible of developing a method which solves the problem in finite number. The algorithm operation solving an application problem. The performance of the algorithm was measured using the execution time and comparing the obtained solutions with those corresponding to the single-level-reformulation. We use a Lagrange relaxation algorithm, it is possible to find a global solution efficiently We propose an algorithm to solve the discrete continuous bi-level problem with result very close to the optimum. Lagrange relaxation is applied to the reformulation to a single level of the problem considering and the binary variables are relaxed for the construction of the Lagrange sub-problem.

References

[1] Von Stackelberg, H. (1934) Marktform und gleichgewicht. Springer, Berlin [2] Bracken, J. and McGill, J. (1973) Mathematical Programs with Optimization Problems in the Constraints. Operation Research, 21, 37-44. https://doi.org/10.1287/opre.21.1.37 [3] Candler, W. and Norton, R. (1977) Multilevel Programming and Development Policy. Technical Report 258, Word Bank Staff, Washington DC. [4] Wen, U. and Hsu, S. (1992) Efficient Solution for the Linear Bilevel Programming Problems. European Journal of Operation Research, 62, 354-362. [5] Jan, R. and Chern, M. (1994) Nonlinear Integer Bilevel Programming. European Journal of Operation Research, 72, 574-587. [6] Liu, Y. and hart, S. (1994) Characterizing an Optimal Solution to the Linear Bilevel Programming Problem. European Journal of Operation Research, 73, 164-166. [7] Liu, Y. and Spencert, T. (1995) Solving a Bilevel Linear Program When the Inner Decision Maker Controls Few Variables. European Journal of Operation Research, 81, 644-651. [8] Ben-Ayed, O. and Blair, C.E. (1990) Computational Difficulties of Bilevel Linear Programming. Operations Research, 38, 556-560. [9] Dempe, S. (2003) Annotated Bibliography on Bilevel Programming and Mathematical Programs with Equilibrium Constraints. Optimization, 52, 333-359. [10] Vicente, L., Savard, G. and Judice, J. (1996) Discrete Linear Bilevel Programming Problem. Journal of Optimization Theory and Applications, 89, 597-614. [11] Ko, C.A. (2005) Global Optimization of Mixed-Integer Bilevel Programming Problems. Computational Management Science, 2, 181-212. [12] Faísca, N.P., Dua, V., Rustem, B., Saraiva, P.M. and Pistikopoulos, E.N. (2007) Parametric Global Optimisation for Bilevel Programming. Journal of Global Optimization, 38, 609-623. [13] Mishra, V.N. (2007) Some Problems on Approximations of Functions in Banach Spaces. PhD Thesis, Indian Institute of Technology, Roorkee, 247-667. [14] Moore, J.T. and Bard, J.F. (1990) Mixed Integer Linear Bilevel Programming Problem. Operations Research, 38, 911-921. [15] Wen, U.P. and Yang, Y.H. (1990) Algorithms for Solving the Mixed Integer Two-Level Linear Programming Problem. Computers and Operations Research, 17, 133-142. [16] Bard, J.F. and Moore, J.T. (1992) an Algorithm for the Discrete Bilevel Programming Problem. Naval Research Logistics, 39, 419-435. [17] Edmunds, T.A. and Bard, J.F. (1992) an Algorithm for the Mixed-Integer Nonlinear Bilevel Programming Problem. Annals of Operations Research, 34, 149-162. [18] Dempe, S. (2003) Annotated Bibliography on Bilevel Programming and Mathematical Programs with Equilibrium Constraints. Optimization, 52, 333-359. [19] Vicente, L., Savard, G. and Judice, J. (1996) Discrete Linear Bilevel Programming Problem. Journal of Optimization Theory and Applications, 89, 597-614. [20] Ko, C.A. (2005) Global Optimization of Mixed-Integer Bilevel Programming Problems. Computational Management Science, 2, 181-212. [21] Faísca, N.P., Dua, V., Rustem, B., Saraiva, P.M. and Pistikopoulos, E.N. (2007) Parametric Global Optimisation for Bilevel Programming. Journal of Global Optimization, 38, 609-623. [22] Domínguez, L.F. and Pistikopoulos, E.N. (2010) Multiparametric Programming Based Algorithms for Pure Integer and Mixed-Integer Bilevel Programming Problems. Computers and Chemical Engineering, 34, 2097-2106. [23] Ben-Ayed, O. (1993) Bilevel Linear Programming. Computers and Operation Research, 20, 485-501. [24] Haurie, A., Savard, G. and White, J.C. (1990) A Note on an Efficient Point Algorithm for a Linear Two-Stage Optimization Problem. Operation Research, 38, 553- 555. https://doi.org/10.1287/opre.38.3.553 [25] Onal, H. (1993) A Modified Simplex Approach for Solving Bilevel Linear Programming Problems. European Journal of Operation Research, 67, 126-135. [26] Husain, S., Gupta, S. and Mishra, V.N. (2013) An Existence Theorem of Solutions for the System of Generalized Vector Quasi-Variational Inequalities. American Journal of Operations Research, 3, 329-336. [27] Gupta, S., Dalal, U.D. and Mishra, V.N. (2014) Novel Analytical Approach of Non-Conventional Mapping Scheme with Discrete Hartley Transform in OFDM System. American Journal of Operations Research, 4, 281-292. [28] Ahmad, I., Mishra, V.N., Ahmad, R. and Rahaman, M. (2016) An Iterative Algorithm for a System of Generalized Implicit Variational Inclusions. Springer Plus, 5, 1283. [29] Judice, J. and Faustino, A. (1994) the Linear Quadratic Bi-Level Programming Problem. INFOR, 32, 87-98. [30] Gupta, S., Dalal, U.D. and Mishra, V.N. (2014) Novel Analytical Approach of Non-Conventional Mapping Scheme with Discrete Hartley Transform in OFDM System. American Journal of Operations Research, 4, 281-292. [31] Dempe, S. (2002) Foundations of Bilevel Programming. Springer Science & Business Media, Berlin.

Copyright

Copyright © 2024 Anil Raj, Dr. Krishnandan Prasad. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.