# Has anybody tried to use the CVX to solve the multi-commodity flow (MCF) problem?

Hi guys, I want to solve the MCF problem using the CVX, but I do not know how to transform the objective and the constraints into the form that are suitable for the CVX to solve. If you have done this before, I hope you could give me some hints on this subject or we could solve this problem together if you are just interested in this problem?

Thanks!

It’s just an LP, right? (Possibly mixed-integer.) I’m not seeing why this would be any more difficult in CVX than any other modeling framework, then. But no I haven’t solved it.

I am trying to solve the MCF problem shown in paper HALO (http://people.ece.cornell.edu/atang/pub/14/HALO_ToN.pdf) using CVX. I am a newbie to CVX, and I think the MCF problem is whorthy trying. Yet the CVX shows that the problem is infeasible. The code is listed below, hoping somebody could possibly point out where the problem would be.

Thanks!

CODE:

``````% using cvx to solve the mcf problem

clear;
clc;
cvx_clear;

% Abilene network topology
%       A B C D E F G H I J K
Topo = [0 1 0 0 0 0 0 0 0 0 1;  % A
1 0 1 0 0 0 0 0 0 0 1;  % B
0 1 0 1 0 0 0 0 0 0 0;  % C
0 0 1 0 1 0 0 0 0 1 0;  % D
0 0 0 1 0 1 0 0 1 0 0;  % E
0 0 0 0 1 0 1 0 0 0 0;  % F
0 0 0 0 0 1 0 1 0 0 0;  % G
0 0 0 0 0 0 1 0 1 0 0;  % H
0 0 0 0 1 0 0 1 0 1 0;  % I
0 0 0 1 0 0 0 0 1 0 1;  % J
1 1 0 0 0 0 0 0 0 1 0;  % K
];

% number of the node in the network
nodeNum = size(Topo, 1);

% number of the directed edge in the network
edgeNum = sum(sum(Topo));

% static demand matrix (just a placeholder)
%D = [];

% randomly generate the demand matrix
upper = 100;
lower = 10;
D = unidrnd(upper, nodeNum, nodeNum);
for iter = 1:nodeNum
D(iter, iter) = 0;
end

for inode = 1:nodeNum
for jnode = 1:nodeNum
if D(inode, jnode) < 50
D(inode, jnode) = 0;
end
end
end

% fixed capacity of every link int the network
C = 300;

% construct the objective fuction and the constraints
cvx_begin
% declare the variables
expression fuvt(nodeNum, nodeNum, nodeNum);

% declare the intermediate and the final objective functions
expression sumobjective(edgeNum);
expression mcfobj(edgeNum + 1);
mcfobj(1) = 0;

% assign the initial value
for inode = 1:nodeNum
for jnode = 1:nodeNum
if Topo(inode, jnode) == 0
for tnode = 1:nodeNum
fuvt(inode, jnode, tnode) = 0;
end
elseif Topo(inode, jnode) == 1
%
fuvt(inode, jnode, inode) = 0;
end
end
end

% edge constraints
% edge index
iedge = 1;
for inode = 1:nodeNum
for jnode = 1:nodeNum
if Topo(inode, jnode) == 1
% edge should bigger than zero
fuvt(inode, jnode, :) >= 0;

% the total flow on the link should no more than the link's capacity
sumobjective(iedge) = sum(fuvt(inode, jnode, :));
sumobjective(iedge) <= C;

iedge = iedge + 1;
end
end
end

%
for inode = 1:nodeNum
for jnode = 1:nodeNum
if D(inode, jnode) > 0 && inode ~= jnode
% flow conservation
sum(fuvt(inode, :, jnode)) - sum(fuvt(:, inode, jnode)) == D(inode, jnode);

end
end
end

% objective functions
iedge = 1;
for inode = 1:nodeNum
for jnode = 1:nodeNum
if Topo(inode, jnode) == 1
mcfobj(iedge + 1) = mcfobj(iedge) + sumobjective(iedge) / (C - sumobjective(iedge));
iedge = iedge + 1;
end
end
end

% minimize the final objective function
minimize(mcfobj(edgeNum + 1));

cvx_end
``````

CODE END