incorrect max-flow problem formulation in MILP tutorial

[maxale]

Is there an existing issue for this?

• [X] I have searched the existing issues for a bug report that matches the one I want to file, without success.

Did you read the documentation and troubleshoot guide?

• [X] I have read the documentation and troubleshoot guide

Environment

N/A

Steps To Reproduce

In the tutorial "Linear Programming (Mixed Integer)" in the section "Flows" at https://doc.sagemath.org/html/en/thematic_tutorials/linear_programming.html#flows the objective function is incorrect.

Expected Behavior

The objective function should be stated as $$\textrm{Max}:\quad\sum{su\in G} f{su} - \sum{vs\in G} f{vs}$$ with the corresponding code:

p.set_objective(p.sum(f[s,u] for u in g.neighbors_out(s)) - p.sum(f[v,s] for v in g.neighbors_in(s)))

Actual Behavior

The objective function is currently stated as $$\textrm{Max}:\quad\sum{sv\in G} f{sv}$$ with the corresponding code:

p.set_objective(p.sum(f[s,u] for u in g.neighbors_out(s)))

Sometimes it produces an incorrect solution.

Additional Information

As a reference, e.g. see this lecture notes: https://www.cs.cmu.edu/~odonnell/toolkit13/lecture14.pdf

[mkoeppe]

It's a common simplifying assumption that the distinguished source node has no incoming arcs; in this situation, the simpler formulation can be used. To fix it, either the proposed change is fine (best if accompanied by an example that includes a circulation through s); or the assumption should be stated.

[maxale]

In the given graph example graphs.ChvatalGraph().minimum_outdegree_orientation() the assumption that source s = 0 has no incoming edges does not hold.

[mkoeppe]

Thanks for checking. I'll be happy to review a PR

[vaswin0]

Please assign this to me @mkoeppe

[anshu129]

Hi @mkoeppe , I think my code can address to the issue from sage.numerical.mip import MixedIntegerLinearProgram

Create the Chvatal graph and its orientation

g = graphs.ChvatalGraph() g = g.minimum_outdegree_orientation()

p = MixedIntegerLinearProgram() f = p.new_variable(real=True, nonnegative=True) s, t = 0, 2

Flow conservation constraints for all vertices (including s)

for v in g: p.add_constraint( p.sum(f[v, u] for u in g.neighbors_out(v))

• p.sum(f[u, v] for u in g.neighbors_in(v)) == 0)

Capacity constraints for all edges

for e in g.edges(labels=False): p.add_constraint(f[e] <= 1)

The objective function for maximizing flow from s to t

p.set_objective(p.sum(f[s, u] for u in g.neighbors_out(s)) - p.sum(f[v, s] for v in g.neighbors_in(s)))

Solve the linear program

p.solve() # rel tol 2e-11

Can I get assigned to this problem?

[maxale]

@anshu129 - why do you ask for assignment? Just create a pull request and give a link here.

[anshu129]

@maxale sorry, I didn't know at that time how to create a pr, I thought maybe getting assigned is related to pr . I will try to solve the issue and create a PR. Thank you

[anshu129]

@maxale, could you please review the PR and let me know if any changes are required? thank you

[maxale]

@anshu129, you corrected the code, but forgot about the problem formulation in LaTeX just before that (line 389 in linear_programming.rst Also, please run the updated code and make sure the present execution results are consistent with the update.

[anshu129]

@maxale I have tried to changing the latex function in linear_programming.rst , I don't have much idea about latex, can you plz tell me if any new constraint should be added .

[maxale]

@anshu129: Change \text{Max: } & \sum_{sv \in G} f_{sv}\\ to \text{Max: } & \sum_{su \in G} f_{su} - \sum_{vs\in G} f_{vs}\\

[anshu129]

@maxale : I changed the function \text{Max: } & \sum{su \in G} f{su} - \sum{sv\in G} f{sv}\ to
\text{Max: } & \sum{su \in G} f{su} - \sum{vs\in G} f{vs}\ in my 3rd commit, can you check it out , and tell me any other change

[maxale]

PR looks good to me now.

[anshu129]

@maxale can you review the PR and close it .

[maxale]

@anshu129 I do not have reviewing priviledge.

[anshu129]

@mkoeppe can you review the PR and close it .