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

1

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!

2

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.

3

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