The hybrid algorithm for solving the three-level linear programming problem
A procedure for solving three-level linear programming is developed and implemented. As an example of three-level problems the distribution of a Federal budget among several states is described. Each state has a number of cities and each city a number of objects for possible funding. A certain number of units is to be allocated to each state. The three-level hierarchy of city, state and Federal Government frequently generates interesting three-level programming problems. The restrictions consist of three sets S 1, S 2, S 3 for the objective functions f 1, f 2, f 3. S 2 and S 3 do not need to be convex. Therefore the analyzed problems involve the optimization of a linear function f over a nonconvex region. A hybrid algorithm is proposed to solve it. It is based on the following result: ``Each extreme point of S 3 is also an extreme point of S 2 and of S 1. The algorithm adopts the ``kth-best algorithm to generate the kth best extreme point by maximizing f 3 over S 1 and a complementary pivot algorithm to check for feasibility in S 3. If the kth best extreme is in S 3 the algorithm terminates with the global optimum; otherwise the \((k+1)th\) extreme point is found by examining adjacent extreme points. The verification of the feasibility in S 3 requires to solve three linear programming problems and an equation system by using the restricted basic entry procedure in the parametric complementary pivot algorithm. The convergence of the algorithm is also analyzed. Cycling can be prevented by storing the basic indexes of each point and checking, for possible duplications, by the generation of the extreme points. By this generation the possible duplications should be checked in order to prevent cycles. The complementary pivot algorithm requires several assumptions. To illustrate the hybrid algorithm a numerical example on \(R^ 3\) is solved. The authors report that the algorithm was coded in Fortran IV. A group of problems with 8 constraints and 20 variables is tested. For the purpose of analyzing the time consuming parts of the program the time spent for performing the difference steps is provided. The execution time is also given for different degrees of control by each level. Furthermore the number of checkings, executed during the solution procedure, is tabulated.
- An investigation of the linear three level programming problem
- An algorithm for non-linear multi-level integer programming problems
- On the nonlinear multilevel programming problems
- A global optimization algorithm for solving linear multilevel programming problem
- scientific article; zbMATH DE number 4127000
- An algorithm for multi-level programming problem using goal programming
- A note on a linear bilevel programming algorithm based on bicriteria programming
- Interactive fuzzy programming for multi-level 0-1 programming problems through genetic algorithms
- Multi-level programming and conflict resolution
- Efficient solutions for the linear bilevel programming problem
- A modified simplex approach for solving bilevel linear programming problems
- Characterizing an optimal solution to the linear bilevel programming problem
- Bilevel and multilevel programming: A bibliography review
- Links between linear bilevel and mixed 0-1 programming problems
- Penalty function approach to linear trilevel programming
- Compensatory fuzzy multiple level decision making
- Interactive fuzzy programming for multilevel linear programming problems
- A multi-level nonlinear multi-objective decision-making under fuzziness
- Adjustable robust optimization through multi-parametric programming
- A modification of the trilevel \(K\)th-best algorithm
- Multi-parametric global optimization approach for tri-level mixed-integer linear optimization problems
- A bi-level non-linear multi-objective decision making under fuzziness.
- Bi-objective bilevel programming problem: a fuzzy approach
- An investigation of the linear three level programming problem
- Interactive fuzzy random two-level linear programming through fractile criterion optimization
- On bilevel fractional programming
- Bilevel optimization: theory, algorithms, applications and a bibliography
- Two theorems on multilevel programming problems with dominated objective functions
- Branch-and-cut solution approach for multilevel mixed integer linear programming problems
- A new exact solution method for bi-level linear fractional problems with multi-valued optimal reaction map
- Bi-level programming and multi-objective optimization for the distribution of resources in hierarchical organizations
- Interactive compensatory fuzzy programming for decentralized multi-level linear programming (DMLLP) problems
This page was built for publication: The hybrid algorithm for solving the three-level linear programming problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1102192)
