The hybrid algorithm for solving the three-level linear programming problem (Q1102192): Difference between revisions

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.