5
$\begingroup$

When creating a network flow formulation you can set up sinks with integer flow requirement $\ge 1$. This yields solutions with the total amount of flow along an edge.

I have also seen this as a real positive number between $0$ and $1$, the latter inclusive (i.e. $(0,1]$). Derived by dividing the sink demand by the total demand.

What are the benefits of the approaches or are they considered equivalent?

$\endgroup$
3
  • $\begingroup$ So you are not asking about requiring integer demands vs allowing demands to be fractional; but rather leaving demands in units vs normalizing them so they are all in [0,1], correct? $\endgroup$
    – LarrySnyder610
    Jun 14 '19 at 16:22
  • $\begingroup$ @LarrySnyder610 yes correct $\endgroup$
    – fhk
    Jun 14 '19 at 16:34
  • 1
    $\begingroup$ Do you have some references? When changing only units the models are equivalent, and that should make no difference in solving time. Looks like a question of preference or convenience in modeling. $\endgroup$ Jun 14 '19 at 23:31
6
$\begingroup$

If you are simply normalizing the demand, then you are essentially solving the same problem.

I would argue that the main benefit of integer capacities is from the modeling viewpoint. When solving a maximum flow problem, for example, having integer capacities in the arcs implies that every optimal basic solution satisfies integrality. Hence, if you have an integer programming problem that could be cast as a maximum flow problem with integer capacities, then you have a linear programming formulation that solves your problem and is considerably cheaper than an integer programming formulation in general.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.