TY - GEN

T1 - On the effectiveness of the linear programming relaxation of the 0-1 multi-commodity minimum cost network flow problem

AU - Choi, Dae Sik

AU - Choi, In Chan

PY - 2006

Y1 - 2006

N2 - Several studies have reported that the linear program relaxation of integer multi-commodity network flow problems often provides integer optimal solutions. We explore this phenomenon with a 0-1 multi-commodity network with mutual arc capacity constraints. Characteristics of basic solutions in the linear programming relaxation problem of the 0-1 multi-commodity problem are identified. Specifically, necessary conditions for a linear programming relaxation to have a non-integer solution are presented. Based on the observed characteristics, a simple illustrative example problem is constructed to show that its LP relaxation problem has integer optimal solutions with a relatively high probability. Furthermore, to investigate whether or not and under what conditions this tendency applies to large-sized problems, we have carried out computational experiments by using randomly generated problem instances. The results of our computational experiment indicate that there exists a narrow band of arc density in which the 0-1 multi-commodity problems possess no integer optimal solutions.

AB - Several studies have reported that the linear program relaxation of integer multi-commodity network flow problems often provides integer optimal solutions. We explore this phenomenon with a 0-1 multi-commodity network with mutual arc capacity constraints. Characteristics of basic solutions in the linear programming relaxation problem of the 0-1 multi-commodity problem are identified. Specifically, necessary conditions for a linear programming relaxation to have a non-integer solution are presented. Based on the observed characteristics, a simple illustrative example problem is constructed to show that its LP relaxation problem has integer optimal solutions with a relatively high probability. Furthermore, to investigate whether or not and under what conditions this tendency applies to large-sized problems, we have carried out computational experiments by using randomly generated problem instances. The results of our computational experiment indicate that there exists a narrow band of arc density in which the 0-1 multi-commodity problems possess no integer optimal solutions.

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

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

M3 - Conference contribution

AN - SCOPUS:33749561172

SN - 3540369252

SN - 9783540369257

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 517

EP - 526

BT - Computing and Combinatorics - 12th Annual International Conference, COCOON 2006, Proceedings

PB - Springer Verlag

T2 - 12th Annual International Conference on Computing and Combinatorics, COCOON 2006

Y2 - 15 August 2006 through 18 August 2006

ER -