Hi there,
I'm wondering if anyone here is able to identify the following problem
better than I've done so far, specifically, I'm interested in finding
out if there are known cuts or valid inequalities out there that I
haven't come accross. We've been able to find some cuts here, but only
for a much weaker model of this problem (basically a capacitated
fixed-charge network). I want cuts for the strong version below,
though.
Here it is: I have a directed graph G={V,E} - very simple, a grid (the
set E connects each vertex to its 4 neighboring vertecies, the edges go
both ways for each 'connection'). I have a set of 'terminal sets' (for
simplicity let's consider pairs only) that belong to V (we call these
'nets'). Consider the 2-net problem: 4 vertices, 2 sets, 2 nets. The
goal is to find connecting 'traces' (sets of vertices) that do not
intersect. This is like wiring an electrical circuit.
So far we've decided to go with a flow formulation. We have flow
variables 'f^k_e' and connectivity variables 'c^k_e', where 'f^k_e = 1'
means there is a flow between vertices i and j (that is, on 'edge e')
for a particular net k, and 'c^k_e = 1' means there is a connection
that allows it for net k. So the first constraint is 'f^k_e >= c^k_e'
(you see the capacitated network here). Flow constraints are imposed
on the vertices: \sum_N(i-) f_e = D_i (N(i-): sum performed over the 4
neighbors into i, D_i the 'demand' at a sink terminal = -1, or the
'supply' at a source terminal = +1, and 0 if not a terminal). The
reason for the c^k_e is: \sum_k \sum_N(i-) c^k_e <= 1 (for all e)
prevents different nets (k) from crossing (at most one k has a '1'
c^k_e going into vertex i). This constraint makes the problem quite
difficult to solve and (for me at least) to classify. Finally \sum_k
c^k_e go in the objective, c \in {0,1}, f \in [0,1].
Please excuse the liberties I've taken with the notation.
So any takers? Any references would be very appreciated.
Thanks in advance.
Ivan.

selecao06 wrote:
Hi there,

I'm wondering if anyone here is able to identify the following problem
better than I've done so far, specifically, I'm interested in finding
out if there are known cuts or valid inequalities out there that I
haven't come accross. We've been able to find some cuts here, but only
for a much weaker model of this problem (basically a capacitated
fixed-charge network). I want cuts for the strong version below,
though.

Here it is: I have a directed graph G={V,E} - very simple, a grid (the
set E connects each vertex to its 4 neighboring vertecies, the edges go
both ways for each 'connection').

Does this mean that between adjacent nodes i and j there are two
separate arcs, one in each direction, or do you mean that all edges are
undirected (in which case it's an undirected graph)?

I have a set of 'terminal sets' (for
simplicity let's consider pairs only) that belong to V (we call these
'nets'). Consider the 2-net problem: 4 vertices, 2 sets, 2 nets.

Sorry, I'm lost on the distinction between "set" and "net", although I
don't think it will affect my answer here.

The
goal is to find connecting 'traces' (sets of vertices) that do not
intersect. This is like wiring an electrical circuit.

So far we've decided to go with a flow formulation. We have flow
variables 'f^k_e' and connectivity variables 'c^k_e', where 'f^k_e = 1'
means there is a flow between vertices i and j (that is, on 'edge e')
for a particular net k, and 'c^k_e = 1' means there is a connection
that allows it for net k. So the first constraint is 'f^k_e >= c^k_e'

Do you mean f^k_e <= c^k_e?

(you see the capacitated network here). Flow constraints are imposed
on the vertices: \sum_N(i-) f_e = D_i (N(i-): sum performed over the 4
neighbors into i, D_i the 'demand' at a sink terminal = -1, or the
'supply' at a source terminal = +1, and 0 if not a terminal). The
reason for the c^k_e is: \sum_k \sum_N(i-) c^k_e <= 1 (for all e)
prevents different nets (k) from crossing (at most one k has a '1'
c^k_e going into vertex i). This constraint makes the problem quite
difficult to solve and (for me at least) to classify. Finally \sum_k
c^k_e go in the objective, c \in {0,1}, f \in [0,1].

Please excuse the liberties I've taken with the notation.

So any takers? Any references would be very appreciated.

Well, I'm not sure, but I think you've got something akin to a
multicommodity network flow with a side constraint that at most one
commodity flows across any arc/edge. So you might try Googling
multicommodity + network + "edge-disjoint" and see if anything useful
pops up. (I tried this myself, but I'm in a coffee shop with a
connection that could use a serious jolt of caffeine, if you know what I
mean. Before things timed out, I did see some promising hits.)

/Paul

Hi Paul,

Thanks for responding to the post.

Does this mean that between adjacent nodes i and j there are two
separate arcs, one in each direction, or do you mean that all edges are
undirected (in which case it's an undirected graph)?

Your first guess - two separate, directed arcs between each pair of
neighboring nodes.

Sorry, I'm lost on the distinction between "set" and "net", although I
don't think it will affect my answer here.

That's because my explanation was confusing. A terminal set = a net.

Do you mean f^k_e <= c^k_e?

Yes, absolutely - sorry.

Well, I'm not sure, but I think you've got something akin to a
multicommodity network flow with a side constraint that at most one
commodity flows across any arc/edge. So you might try Googling
multicommodity + network + "edge-disjoint" and see if anything useful
pops up. (I tried this myself, but I'm in a coffee shop with a
connection that could use a serious jolt of caffeine, if you know what I
mean. Before things timed out, I did see some promising hits.)

Thanks for that tip. I haven't found anything on the cut strategy side
of things, but the formulation side has been quite interesting. The
"edge-disjoint" search gave me a lot of interesting hits. I really
like the approach taken by some where "paths" are defined as
*variables* on the grid (similar to what I called "traces"). Clearly
there is an astronomical number of such paths, so I'm wondering if I
can keep this in the MIP domain by using a column generation strategy
to incorporate the available paths. I wonder, however, if I'm
approaching this problem all wrong with a MIP branch-and-bound solution
methodology, while approximation algorithms ala

http://www.cs.umd.edu/~srin/PDF/edge-dis.pdf

and

are more appropriate for this problem. We've found that we can solve
problems of less than 10 nets pretty well with our branch-and-bound
strategy, but bigger problems become quite a headache (especially as
the graph grows). Any insight on wheather the approaches above may be
more favorable?

Thanks.

selecao06 wrote:
>Well, I'm not sure, but I think you've got something akin to a
>multicommodity network flow with a side constraint that at most one
>commodity flows across any arc/edge. So you might try Googling
>multicommodity + network + "edge-disjoint" and see if anything useful
>pops up. (I tried this myself, but I'm in a coffee shop with a
>connection that could use a serious jolt of caffeine, if you know what I
>mean. Before things timed out, I did see some promising hits.)
>
Thanks for that tip. I haven't found anything on the cut strategy side
of things, but the formulation side has been quite interesting. The
"edge-disjoint" search gave me a lot of interesting hits. I really
like the approach taken by some where "paths" are defined as
*variables* on the grid (similar to what I called "traces"). Clearly
there is an astronomical number of such paths, so I'm wondering if I
can keep this in the MIP domain by using a column generation strategy
to incorporate the available paths.

Major disclaimer: I can spell "multicommodity" (given two tries and a
spellchecker), but I don't read the relevant literature and can't say
anything specific about them.

Using a column generation approach with variables representing paths
rather than arcs is a possibility. It takes you into the arena of
branch-and-price, not to be confused with branch-and-cut or
branch-and-bound (where you add just cuts, not new variables). There's
a fair bit of literature on using branch-and-price for large problems,
including (prominently) crew scheduling applications, which I think
resemble what you're discussing here (variables become assignments to
routes rather than just individual legs). You would need, I think, to
add SS1 constraints preventing the use of two routes that intersect on
an arc.

As far as cuts go, if I'm reading the problem correctly then the
following is a valid cut (although possibly not a helpful one). Given a
node j, let E_{0j} = {(i,j) \in E} and E_{1j} = {(j,i) \in E}. Then for
any net (?) k such that node j is not a sink for net k,

\sum_{e \in E_{0j}} c^k_e \le \sum_{e in E_{1j}} c^k_{e'}.

If j is not a source for net k, the reverse inequality is a valid cut.
Assuming your solver supports constraint pools or lazy constraints or
whatever the vendor chooses to call them, you can either add these
constraints up front but leave them out of the active working model
until they are violated, or you can generate them on the fly as cuts.

I wonder, however, if I'm
approaching this problem all wrong with a MIP branch-and-bound solution
methodology, while approximation algorithms ala

http://www.cs.umd.edu/~srin/PDF/edge-dis.pdf

and

are more appropriate for this problem. We've found that we can solve
problems of less than 10 nets pretty well with our branch-and-bound
strategy, but bigger problems become quite a headache (especially as
the graph grows). Any insight on wheather the approaches above may be
more favorable?

Sorry, outside my scope.

/Paul

Hi Paul,

Thanks for the input.

Yes, we had considered the cut you suggested and unfortunately it
doesn't help strengthen the formulation that we currently have. We do
have a weaker formulation where these cuts come in handy, but we
seriously sacrifice lower bounds in that case so we decided to stick to
the stronger formulation - which has caused me to pick my brain
endlessly without being able to formulate a useful cut. Too bad

I've looked up some lit on the crew scheduling approach based on
branch-and-price and things seem to be lining up that way. Maybe the
path-based approach is the way to go. This has really opened up a new
way of thinking about the problem that I hadn't considered before -
that's cool.

Thanks for the help!

Ivan.

I'm still struggling with understanding the problem.
Given a directed graph do you have pairs of nodes
that need to be connected with paths, one for each pair,
that do not have a common vertex?