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 languageEnglish
Pages (from-to)393-398
Number of pages6
JournalEuropean Journal of Operational Research
Volume46
Issue number3
DOIs
Publication statusPublished - 1990
Externally publishedYes

    Research areas

  • Cross decompositionb, Kornai-Liptak algorithm, convergence, mathematical programming

ID: 47551007