Performance analysis of a parallel Dantzig-Wolfe decomposition algorithm for linear programming

Jrjung Lyu, Hsing Luh, Ming Chang Lee

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

This paper employs the Dantzig-Wolfe decomposition principle to solve linear programming models in a parallel-computing environment. Adopting the queuing discipline, we showed that under very general conditions, the proposed algorithm speedup trends toward a limiting value as the number of processors increases.

Original languageEnglish
Pages (from-to)1431-1437
Number of pages7
JournalComputers and Mathematics with Applications
Volume44
Issue number10-11
DOIs
Publication statusPublished - 2002 Nov 1

Fingerprint

Dantzig-Wolfe Decomposition
Queuing
Decomposition Algorithm
Parallel processing systems
Parallel Computing
Linear programming
Programming Model
Performance Analysis
Linear Model
Speedup
Limiting
Decomposition
Trends

All Science Journal Classification (ASJC) codes

  • Modelling and Simulation
  • Computational Theory and Mathematics
  • Computational Mathematics

Cite this

@article{f9339cf578aa4d208ac966f963e11167,
title = "Performance analysis of a parallel Dantzig-Wolfe decomposition algorithm for linear programming",
abstract = "This paper employs the Dantzig-Wolfe decomposition principle to solve linear programming models in a parallel-computing environment. Adopting the queuing discipline, we showed that under very general conditions, the proposed algorithm speedup trends toward a limiting value as the number of processors increases.",
author = "Jrjung Lyu and Hsing Luh and Lee, {Ming Chang}",
year = "2002",
month = "11",
day = "1",
doi = "10.1016/S0898-1221(02)00267-5",
language = "English",
volume = "44",
pages = "1431--1437",
journal = "Computers and Mathematics with Applications",
issn = "0898-1221",
publisher = "Elsevier Limited",
number = "10-11",

}

Performance analysis of a parallel Dantzig-Wolfe decomposition algorithm for linear programming. / Lyu, Jrjung; Luh, Hsing; Lee, Ming Chang.

In: Computers and Mathematics with Applications, Vol. 44, No. 10-11, 01.11.2002, p. 1431-1437.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Performance analysis of a parallel Dantzig-Wolfe decomposition algorithm for linear programming

AU - Lyu, Jrjung

AU - Luh, Hsing

AU - Lee, Ming Chang

PY - 2002/11/1

Y1 - 2002/11/1

N2 - This paper employs the Dantzig-Wolfe decomposition principle to solve linear programming models in a parallel-computing environment. Adopting the queuing discipline, we showed that under very general conditions, the proposed algorithm speedup trends toward a limiting value as the number of processors increases.

AB - This paper employs the Dantzig-Wolfe decomposition principle to solve linear programming models in a parallel-computing environment. Adopting the queuing discipline, we showed that under very general conditions, the proposed algorithm speedup trends toward a limiting value as the number of processors increases.

UR - http://www.scopus.com/inward/record.url?scp=0036857096&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036857096&partnerID=8YFLogxK

U2 - 10.1016/S0898-1221(02)00267-5

DO - 10.1016/S0898-1221(02)00267-5

M3 - Article

VL - 44

SP - 1431

EP - 1437

JO - Computers and Mathematics with Applications

JF - Computers and Mathematics with Applications

SN - 0898-1221

IS - 10-11

ER -