[FlopCpp] Issue with constraint formulation

Alfredo Olivera aolivera at fing.edu.uy
Wed Mar 12 15:07:24 EDT 2008


Hi All.

I am new to this library, and to give my first steps I decided to 
formulate a min cost s-t flow problem in a capacitated network with 
FlopC++. That is, I have to send U units of flow from s to t subject to 
capacity constraints and with minimum cost.

I have my sets of nodes and arcs:
    int n = 10;
    MP_set Nodes(n);
    MP_subset<2> Arcs(Nodes, Nodes);

I populate the arcs randomly.

My parameters are:
    MP_data Capacity(Arcs);
    MP_data Cost(Arcs);

And the variables are defined over the arcs (not over nodes*nodes):
    MP_variable x(Arcs);

I also have s and t defined as integer variables, and the amount of 
units to send:
    int s = ...; // source
    int t = ...; // terminal
    int U = ...; // units to send

I am having several issues when trying to formulate the constraints. My 
current status is the following:

// flow conservation on inner nodes
    MP_constraint flowCons(Nodes);
    flowCons(i).such_that(i != s && i != t) = sum(Arcs(i,j), 
x(Arcs(i,j))) == sum(Arcs(j,i), x(Arcs(j,i)));

// capacity constraints
    MP_constraint CapacityCons(Arcs);
    CapacityCons(Arcs(i,j)) = x(Arcs(i,j)) <= Capacity(Arcs(i,j));

// send exactly U units out of s
    MP_constraint DemandOut;
    DemandOut() = sum(Arcs(s,j), x(Arcs(s,j))) == U;

Flow conservation and arc capacity seem to be working ok (I generated a 
file with the LP format and checked).

But the DemandOut constraint is not working. The version I put above 
just makes the model generation to crash. I also tried:
    DemandOut() = sum(Arcs(i,j).such_that(i==s), x(Arcs(i,j))) == units;

which does not crash, but sums every variable of the problem instead of 
only those which correspond to (s,i) arcs where s is fixed.

For sure I am making a mistake... but I cannot figure out where. Any 
help would be really appreciated.

Regards

Alfredo Olivera



More information about the FlopCpp mailing list