Min Cut Formulation

[M. S.]

Hello,

I am very new to integer linear programming and trying to solve a
classical problem at the moment, yet I couldn't find anything similar
on the web really.

I want to calculate the minimum cut of a simple network, by actually
enumerating all possible cuts and not by calculating the maximum
flows. The idea is to divide a network with, say, one source, two
relay nodes connected with every other node and two sinks, in all
possible cuts where the sinks and the source are not in the same part
(which should result in four possibilities, if i counted correctly).

Then the connections over the cut shall be counted (all having the
same capacity for the sake of simplicity).

The max flow formulation was easy, but I really am having problems
with this one. Any help or directions where to read more about
implementing this, would be highly appreciated.

Thanks very much!

[Paul]

First comment: the number of cuts grows exponentially with the size of
the network, so be careful what you wish for.

Suppose that you enumerate all paths from source to sink. Assign a
0-1 variable to each arc indicating whether you will (1) or will not
(0) cut it. The problem then becomes a set covering problem, in which
the cover constraints are the sums of the indicators along each path.
The objective is the sum of the indicators, weighted by arc capacity.

To find the minimum cut, you solve the SCP once. To find all cuts,
you can solve the min cut problem (or solve the same problem with a
zero objective function, which might be faster) to get one cut. Then
add a constraint to prevent that cut from repeating and solve again.
Since the variables are all 0-1, the easy way to eliminate a solution
is to say that the sum of those indicators that were 0 in the last
solution plus the sum of the complements (1-variable) of those
indicators that were 1 in the last solution must be >= 1, which forces
at least one change.

Note that each problem you're solving is a 0-1 integer linear program,
not a linear program.

Enumerating all the solutions is a bit easier if you can use callbacks
in a solver (CPLEX, for instance, contains callbacks). Instead of
adding constraints to eliminate solutions as they occur, you can just
record and reject them and keep looking. Unfortunately, it's not
possible to use callbacks from AMPL.

Finally, if you don't want to spend time up front enumerating all
paths from source to sink, you can do it "on the fly" using Benders
decomposition, which is more than I want to get into here.

/Paul

[M. S.]

Hi!

First of all, thanks very much for your answer!

I do know that the problem is NP-hard, but I indeed want the optimal
solutions for small networks (and see how far it can go computing-
wise).

Maybe I should explain my actual problem a bit more. I'm considering
this network (http://dl.dropbox.com/u/1672089/exgraph.png), as
described before, with node 0 being the source and node 4 and 5 being
the sinks, it is only possible for the flows to go from source to the
sinks, so the edges are not bidirectional besides the one between 1
and 2. Source is never directly connected to a sink.

Now, my definition of an s-t cut is the following: The network is cut
in a way that the source is in one side and the sinks are in the the
other partition. Both relay nodes can be on either side, so I have
four possibilities here. Until here I can create such sets in AMPL (or
ZIMPL which I had been using) from a given graph. Then I want to use a
binary variable "sourcepartition", which is assigned to each node
depending on which side of the cut it is in (this already proved
difficult for me, being used to Java and the likes).

Now, the capacity of any cut is "just" adding up
1) the connections from the source to all relay nodes in the sink
partition
2) the connections from the relay nodes in the source partition to the
relay nodes in the sink partition
3) the connections between the relay nodes in the source partition and
the sinks

In the example cut this makes (unsurprisingly) 1 + 1 + 2 = 4.

Now calculating this for all four cuts and getting the minimum cut
would be my dream. :)

The problem is that lacking experience I cannot yet judge if this is
feasible with a mathematical modeling language and respective solvers
and if yes, how to do that properly. Again, performance is really
secondary for the moment, i just want an optimal solution. Later on
the network should of course not be fixed but the solution should work
with any given one, that fulfills the properties.

Any thoughts are welcome!

[Paul]

On Sep 30, 8:11 am, "M. S." <trf-ma...@gmx.net> wrote:
>
> I do know that the problem is NP-hard, but I indeed want the optimal
> solutions for small networks (and see how far it can go computing-
> wise).
>
> Maybe I should explain my actual problem a bit more. I'm considering
> this network (http://dl.dropbox.com/u/1672089/exgraph.png), as
> described before, with node 0 being the source and node 4 and 5 being
> the sinks,

Node 5 wasn't Atlantis by any chance, was it? I only see nodes 0
through 4.

> it is only possible for the flows to go from source to the
> sinks, so the edges are not bidirectional besides the one between 1
> and 2. Source is never directly connected to a sink.
>
> Now, my definition of an s-t cut is the following: The network is cut
> in a way that the source is in one side and the sinks are in the the
> other partition.

I think you are actually dealing with a multicut, then. (See, for
instance, http://ensta.fr/~diam/ro/online/viggo_wwwcompendium/node93.html).
The distinction is whether you're trying to cut all paths from the
source to one of the sink nodes ("cut") or simultaneously cut all
paths to all sink nodes ("multicut").

> Both relay nodes can be on either side, so I have
> four possibilities here. Until here I can create such sets in AMPL (or
> ZIMPL which I had been using) from a given graph. Then I want to use a
> binary variable "sourcepartition", which is assigned to each node
> depending on which side of the cut it is in (this already proved
> difficult for me, being used to Java and the likes).
>
> Now, the capacity of any cut is "just" adding up
> 1) the connections from the source to all relay nodes in the sink
> partition
> 2) the connections from the relay nodes in the source partition to the
> relay nodes in the sink partition
> 3) the connections between the relay nodes in the source partition and
> the sinks
>
> In the example cut this makes (unsurprisingly) 1 + 1 + 2 = 4.
>
> Now calculating this for all four cuts and getting the minimum cut
> would be my dream. :)
>
> The problem is that lacking experience I cannot yet judge if this is
> feasible with a mathematical modeling language and respective solvers

It is.

> and if yes, how to do that properly. Again, performance is really
> secondary for the moment, i just want an optimal solution. Later on
> the network should of course not be fixed but the solution should work
> with any given one, that fulfills the properties.

Let's say you start with the following. (BTW, AMPL has network
specific terminology, but I've never had much call to use it, so I'll
stick to generic forms.)

set NODES; # all the nodes, including sources and sinks
set SOURCES within NODES;
set SINKS within NODES;
set ARCS within NODES cross NODES; # arcs are directional
param capacity {ARCS} >= 0; # arc weights
var sourcepartition {NODES} binary; # 1 if node is in the source
partition, 0 if in the sink partition

Next, we'll throw in some constraints to fix the value of
sourcepartition for terminal nodes:

s.t. IsSource {n in SOURCES}: sourcepartition[n] = 1;
s.t. IsSink {n in SINKS}: sourcepartition[n] = 0;

Now you want to add up the capacities of arcs that cross the cut. In
the interest of minimizing the number of binary variables, we'll sneak
up on this a bit.

var cost{ARCS} >= 0; # 0 if arc does not cross the cut, capacity of
arc if it does

s.t. GetsCut1 {(u, v) in ARCS}: cost[u,v] >=
capacity[u,v]*(sourcepartition[u] - sourcepartition[v]);
s.t. GetsCut2 {(u, v) in ARCS}: cost[u,v] >=
capacity[u,v]*(sourcepartition[v] - sourcepartition[u]);

minimize CutSize: sum {(u,v) in ARCS} cost[u,v];

In the GetsCut* constraints, if sourcepartition[u] =
sourcepartition[v], the RHS of both will be 0, and while it's feasible
for the cost to be positive, minimizing the sum of costs will push the
cost of that arc to 0. If sourcepartition[u] != sourcepartition[v],
the RHS of one of those two constraints will be negative (so the
constraint is vacuous) and the RHS of the other will be the capacity
of the arc, forcing the objective to include at least (and therefore,
since we're minimizing, exactly) the capacity of the arc.

Note the reliance here on the objective "tamping down" the cost[]
variable. If you want to find all cuts irrespective of cost, you'll
have to solve for the minimum cut, add a constraint to bar it, solve
the runner up minimum cut, add a constraint, repeat ad nauseum.

/Paul

PS: I can't recall if cost[u,v] or cost[(u,v)] is the correct AMPL
syntax when indexing by a tuple, and I don't have time right now to
research it. I think it's the former.

[Robert Fourer]

Each cut can be represented as a subset of the arcs. So if you have already
enumerated all of the cuts, then you can represent them as an indexed
collection of arc subsets:

set NODES;

set ARCS within NODES cross NODES;

param nCUTS;
set CUTS {1..nCUTS} within ARCS;

At this point the determination of the length of the minimum cut would not
require any declarations of variables or invocations of a solver:

param length {ARCS};
param mincutlength = min {k in 1..nCUTS} sum {(i,j) in CUTS[k]}
length[i,j];

A little script could loop through all the cuts and determine which have
length equal to the minimum. Of course if you don't know all the cuts then
you will in general have to use an algorithm to determine them, and
conceivably you could write such an algorithm in AMPL, though more general
programming languages might be faster and have more convenient data
structures for the purpose. I don't think that generating all the cuts fits
into the category of things one computes by using an optimization model and
a solver, though.

Bob Fourer
4...@ampl.com