What is the name of this combinatorics/network problem?

[gosper...@yahoo.com]

(This is a repost from sci.math since there was no response there)
I have a flow network with gains, a single source and a single sink.
All capacities and gains are integers, all arcs are directed and
there
are no loops.
I want to maximise the flow on this network.
The flow must be wholly along a single arc leaving a node (i,e, if
arcs (A,B) and (A,C) exist and flow 1 enters node A, there cannot be
.5 flow leaving A along both (A,B) and (A,C), it must be 1 along
either
(A,B) or (A,C)).
I'm trying to find an algorithm that solves such a problem, but I
don't really know what to search for.
Can anyone tell me what the name for this type of problem is?
For bonus points: what algorithm(s) can I use to solve it?
Thank you very much.

[Gordon Sande]

Why not just treat it as a linear program? If you get fractions it will
either be because they are real or because they are an artifact of a
degeneracy. In the latter case change the cost of one of the arcs by
"epsilon".

You might also have to treat the arc flows as complementary. That is only
one of the two can be nonzero. Again, linear complementatity is a pretty
standard topic.

Networks with minor gains hae been called generalized networks (how
original and uninformative!) in some papers I think I recall. Of course
there may be other "generalized" networks.

[Ray Vickson]

On Dec 29, 5:27 pm, Gordon Sande <Gordon.Sa...@gmail.com> wrote:

> On 2011-12-29 20:26:24 -0400, gospervand...@yahoo.com said:
>
>
>
> > (This is a repost from sci.math since there was no response there)
> > I have a flow network with gains, a single source and a single sink.
> > All capacities and gains are integers, all arcs are directed and
> > there
> > are no loops.
> > I want to maximise the flow on this network.
> > The flow must be wholly along a single arc leaving a node (i,e, if
> > arcs (A,B) and (A,C) exist and flow 1 enters node A, there cannot be
> > .5 flow leaving A along both (A,B) and (A,C), it must be 1 along
> > either
> > (A,B) or (A,C)).
> > I'm trying to find an algorithm that solves such a problem, but I
> > don't really know what to search for.
> > Can anyone tell me what the name for this type of problem is?
> > For bonus points: what algorithm(s) can I use to solve it?
> > Thank you very much.
>
> Why not just treat it as a linear program? If you get fractions it will
> either be because they are real or because they are an artifact of a
> degeneracy. In the latter case change the cost of one of the arcs by
> "epsilon".

For a network with gains the integrality property fails; thus, LP is
not guaranteed to work.

If the problem is not too large, a complete enumeration of all paths
seems workable, in which case just enumerating the different flows
seems feasible.

RGV

[gosper...@yahoo.com]

Thank you for all your responses.

> > You might also have to treat the arc flows as complementary. That is only
> > one of the two can be nonzero. Again, linear complementatity is a pretty
> > standard topic.

I will investigate this.

> > For a network with gains the integrality property fails; thus, LP is
> > not guaranteed to work.

Does this mean that if the maximum flow on the network is an integer,
that there are no algorithms that are guaranteed to return the actual
maximum flow? What about non-LP algorithms?

Is the situation any different if I relax the no partial flows
constraint?

Thanks again.

[Ray Vickson]

On Jan 1, 4:37 pm, gospervand...@yahoo.com wrote:
> Thank you for all your responses.
>
> > > You might also have to treat the arc flows as complementary. That is only
> > > one of the two can be nonzero. Again, linear complementatity is a pretty
> > > standard topic.
>
> I will investigate this.
>
> > > For a network with gains the integrality property fails; thus, LP is
> > > not guaranteed to work.
>
> Does this mean that if the maximum flow on the network is an integer,
> that there are no algorithms that are guaranteed to return the actual
> maximum flow? What about non-LP algorithms?

First you need to define what an integer flow is. For example, if an
arc has gain 1.13 (i.e., output = 1.13*input) then which end of the
arc is to have the integer flow? If input = integer, output may not be
integer, and vice-versa.

Anyway, integrality or not was not the issue raised by the OP. The OP
wanted to find the single path having the maximum flow; whether or
not
the flow on that path is integer was not part of the stated problem.

RGV

[Gordon Sande]

Without looking up the thread my memory is that the original posting was for
a "network" in which there were integer gains. There was also a concern about
an otherwise integer flow being split into fractional flows.

All told, not a great set of requirements expressed with clarity and precision.

The sensible thing would be to solve the problem with a fair sized hammer, like
a full LP, and see if the solutions were interesting. Only after there
were solutions
would it make sense to use hindsight to figure out what the important
requirements
would be. For instance, does it matter if the flow takes several paths with all
flows being integer or is it required to be only one path which would
be integer
if the source and all gains were integer. If this is for a toy situation then a
small supply of paper pads should suffice given enough pencils.

The noteworthy feature of networks is that they have been researched to
death with
many pretty results and that those results mean that truly immnese
problems can be
solved in amazingly short times. There are lots of other pieces of
machinery away
from networks that are not so pretty or capable of immense problems but that do
a very workmanilke job for real problems. So solve and then try to find
"elegant'
solution methods.