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?

Improve this question
$\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, 2019 at 16:22
  • $\begingroup$ @LarrySnyder610 yes correct $\endgroup$
    – fhk
    Jun 14, 2019 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$
    – Marcus Ritt
    Jun 14, 2019 at 23:31

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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