On the resemblance between the Kornai-Liptak and cross decomposition techniques for block-angular linear programs

Karen Aardal, Aysen Ari

Research output: Contribution to journalArticleScientificpeer-review

5 Citations (Scopus)

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

Keywords

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

Fingerprint Dive into the research topics of 'On the resemblance between the Kornai-Liptak and cross decomposition techniques for block-angular linear programs'. Together they form a unique fingerprint.

Cite this