Abstract
In this paper the resemblance is demonstrated between the master- and subproblems generated by the Kornai-Liptak algorithm and the subproblems obtained by using the cross decomposition method on linear optimization problems with block-angular structure. The significance of the similarity between these two algorithms becomes apparent considering the main disadvantage attributed to cross decomposition. In cross decomposition a master problem has to be solved from time to time since the subproblems alone do not always give a converging sequence of primal and dual solutions. But if the cross decomposition algorithm is modified in such a way that the successive primal and dual subproblem solutions are taken into consideration with equal weights, this results in the Kornai-Liptak algorithm for which convergence is guaranteed.
Original language | English |
---|---|
Pages (from-to) | 393-398 |
Number of pages | 6 |
Journal | European Journal of Operational Research |
Volume | 46 |
Issue number | 3 |
DOIs | |
Publication status | Published - 1990 |
Externally published | Yes |
Keywords
- Cross decompositionb
- Kornai-Liptak algorithm
- convergence
- mathematical programming