Vol 4 No 2 (2009)

2-Commodity Integer Network Synthesis Problem

S. N. Kabadi
University of New Brunswick
R. Chandrasekaran
University of Texas at Dallas
K. P.K. Nair
University of New Brunswick
How to Cite
Kabadi, S. N., Chandrasekaran, R., & Nair, K. P. (1). 2-Commodity Integer Network Synthesis Problem. Algorithmic Operations Research, 4(2), Pages 117 - 132. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/12477


We consider the following 2-commodity, integer network synthesis problem: Given two n×n, non-negative, symmetric, integer-valued matrices R = (rij) and S = (sij) of minimum flow requirements of 2 different commodities, construct an undirected network G = [N, E, c] on node set N = {1, 2, . . . , n} with integer edge capacities {c(e) : e ∈ E}, such that: (i) for any two pairs (i, j) and (k, l), i ≠ j, k ≠ l, of nodes in N, we can simultaneously send rij units of flow of commodity 1 from i to j and skl units of flow of commodity 2 from k to l in G; and (ii) z = Σ {c(e) : e ∈ E} is minimum. We present strongly polynomial, combinatorial algorithms for certain special cases of the problem; and for the general problem, we present a strongly polynomial, combinatorial algorithm that produces a feasible solution with objective function value no more than (the optimal objective function value +3).