Linear programs (LP) have been used popularly as a practical optimization method in many fields for many years. According to recent diversification of problem-solving, however, we are forced to formulate the problem in difficult and complicated manners. For examples, we can cite multiobjective optimization problems, redesign problems, flexibility design problems, constrained dynamic matrix control problems, mixed-integer linear programming (MILP) problems, and so on. Thereby a family of large complex LP must be solved repeatedly before arriving at a final result. It is very helpful for us to develop special methods that can cope with the above situation effective as well as flexibly while utilizing a certain reference information from the foregoing problem. With this point of view, in this paper, we will propose a method termed progressive linear programs (PROLP), and discuss about its extensions and some applications in chemical processes.
Basically PROLP is a generalized version of PAPA (pivot and probe algorithm). Both methods are relied on the fact the optimal solution is usually made of very small part of the whole set of the constraints in many cases. Hence we can conserve the computational load greatly if we could know the active constraint set a priori. Since it is impossible, we should take a gradual manner, and invent to do it effectively.
First we have developed the procedure applying the dual algorithm in the framework of the two-phase method of simplex method. Starting with a very little number of constraints, the tentative solution will be revised in turn subject to the appropriately augmented constraints before attaining at the optimal. Since success of the procedure depends largely on how to evolve the constraint set, and to utilize the result of the simplex computation in the preceding stage, we should elaborate on these points very carefully when developing PROLP.
Then we have extended our idea as follows. In the case where a similar kind of problems should be solved repeatedly , we can expect to apply PROLP more efficiently by customizing its solution. For this purpose, after diversifying the indices for choosing the additional constraints, we have prepared the neural networks learned the relation between the indices and the fact whether the chosen constraint was active or not. For such a problem-solving with a certain structural characteristic, we can improve daily problem-solving by the proposed extension.
The parametric calculation is another extension considered effective to increase the performance in repeated solution of the similar problems. This is because a family of problem appearing in the problem-solving mentioned above differs only a little from the foregoing one, that is, only (1) a part of right hand side value, (2) coefficients of objective function and so on. For examples, case (1) occurs in the successive solution by branch and bound method for MILP, and case (2) is true associated with the solution of multiobjective optimization. We will present the procedures of the parametric calculations of PROLP for several cases including (1) and (2).
To examine the effectiveness of all our concerns addressed above, numerical experiments will be carried out through randomly generated test problems first. Then a variety of promising applications like mentioned earlier will be presented.
System Create Lab. - Research Areas