Enable <= supply requirement in Network Simplex

[Alpar Juttner]

It is purely and extension of the min. cost flow problem if we only require that the actual supply is at most the the prescription.

This extension does not require substantial change in the algorithm.

[Peter Kovacs]

The attached changeset [cf49ce98b6a4] solves this issue. It depends on [c7d160f73d52], which can be found at ticket #234. Moreover it contains substantial doc improvements for the MCF module and the classes NetworkSimplex and Circulation.

In this patch NetworkSimplex supports exactly the same inequality constraints as Circulation (i.e. lower bounds for the actual supply values), and contains a note about transforming the opposite direction to this form. However it would be nice to support that form, too.

In Circulation it wouldn't be easy, I think, but in NetworkSimplex both directions could be easily supported. The only non-trivial question is the interface for that. If anybody could suggest a good interface, I could implement that form, too.

[Alpar Juttner]

Replying to kpeter:

In Circulation it wouldn't be easy, I think, but in NetworkSimplex both directions could be easily supported. The only non-trivial question is the interface for that. If anybody could suggest a good interface, I could implement that form, too.

E.g.

problemType(SURPLUS_ALLOWED); // Default

and

problemType(DEFICIT_ALLOWED);

the first one may be replaced with

problemType(EXCESS_ALLOWED);

[Alpar Juttner]

By the way, we might want to change the default the DEFICIT_ALLOWED. Strangely enough, it we allow deficit, the it means that all the demands (the negative supply values) must be satisfied, while SURPLUS_ALLOWED means that all the supplies must be led towards the sinks.

Well, it also means that we might want to find some better problem type names. If we can.

[Peter Kovacs]

Replying to alpar:

By the way, we might want to change the default the DEFICIT_ALLOWED. Strangely enough, it we allow deficit, the it means that all the demands (the negative supply values) must be satisfied, while SURPLUS_ALLOWED means that all the supplies must be led towards the sinks.

I don't think so. Let sup_req(u) denote the supply requirement at node u, and sup(u) denote the actual supply/export at node u. The sum of sup(u) values is zero, and let SUM denote the sum of sup_req(u) values.

1. If sup(u) <= sup_req(u) have to be satisfied, then SUM >= 0.
2. If sup(u) >= sup_req(u) have to be satisfied (the available form at Circulation), then SUM <= 0.

It seems to be clear that excess/surplus is when sup(u) < sup_req(u) and deficit is when sup(u) > sup_req(u) both for positive and negative values.

So if we allow excess/surplus, then it is the first case, so all the demands have to satisfied, and if we allow deficit then all supplies have to be carried to the demend nodes, but the demands don't have to be satisfied (that is the sacond case, which is supported by Circulation and the new NetworkSimplex). Am I right?

Moreover NetworkSimplex ensures sup(u) = sup_req(u) for all the nodes with non-negative sup_req value, and allow inequality (deficit) only for the demand nodes (that is for the second case). If it would support the first case as well, it would ensure equality for all the nodes with non-positive sup_req value, and allow inequality (excess/surplus) only for the supply nodes.

This nice property could be kept because the arc costs have to be non-negative. If we allow negative costs in the future (which could be transformed to a problem without negative costs), then this property could not be satisfied. So this porperty could be mentioned in the doc, unless we allow negative costs.

Well, it also means that we might want to find some better problem type names. If we can.

If I'm right in the above explanation, then these names could be acceptable. However I would prefer three-state settings, one additional case for the equality form, although it is a special case for both inequality forms.

[Alpar Juttner]

Replying to kpeter:

It seems to be clear that excess/surplus is when sup(u) < sup_req(u) and deficit is when sup(u) > sup_req(u) both for positive and negative values.

You are definitely wrong here. "Excess/surplus allowed" means that you can have more than what is required, i.e, sup(u) >= sup_req(u).

[Peter Kovacs]

Replying to alpar:

You are definitely wrong here. "Excess/surplus allowed" means that you can have more than what is required, i.e, sup(u) >= sup_req(u).

I think you are worng here. All the books and papers about min. cost flows use the notion excess(u) = sup_req(u) - sup(u). So you have excess if and only if sup(u) < sup_req(u).

Maybe the names are a bit misleading. The actual supply could be called export, and the supply requirement could be called supply. That is what we have (or need, if it is negative) at a node, and the actual supply/export means what we export or import, since it is the difference between the outgoing and incomming flow.

[Peter Kovacs]

Replying to kpeter:

Replying to alpar:

You are definitely wrong here. "Excess/surplus allowed" means that you can have more than what is required, i.e, sup(u) >= sup_req(u).

I've searched for the usage of excess and deficit again related to flow algorithms. Excess is always used for a flow amount that have to be pushed/carried out from the node and deficit used for the opposite. For example the attached picture show a paragraph form the Network Flows book of Ahuja, Magnanti and Orlin. Could you show example for the opposite usage?

Dual algorithms (augmenting path methods) and primal-dual algorithms (e.g. cost scaling push-relabel methods) for the MCF problem, which maintain a pseudoflow, use the notion excess node for a node where the outgoing flow minus the incoming flow is less then the requirement (supply or b), see the attached file. We have positive excess at these nodes and we have to push/carry this excess out from the node. For the well-known preflow algorithm for the max flow problem this notion is also used this way, so the active nodes, from which we can push to other nodes have excess. If we introduce a more general inequality form, we do not have any reason for change the usage of these notions. Moreover this interpretation is at least as logical as your one.

In fact, I do like the names you suggested but definitely want to use them for the opposite case. If we use excess and/or deficit we must use them as everyone else do.

[Peter Kovacs]

Another example for the usage of excess: it is the amount of what we have to push out from a node, not what we have pushed out yet.
​http://en.wikipedia.org/wiki/Push-relabel_maximum_flow_algorithm

Here excess is defined as IN - OUT (for nodes where the supply is zero). A natural generalization is EXCESS = IN - OUT + SUPPLY = SUPPLY - (OUT - IN), see e.g. the Network Flows book. But you would like to use it for (OUT - IN) - SUPPLY.

I probably used misleading and/or incorrect notations for the first time. I used sup_req for what I denote SUPPLY here, and used sup for what I denote (OUT - IN) here.

[Alpar Juttner]

Replying to kpeter:

Could you show example for the opposite usage?

The "common sense" gives a good example for this. If you have any kind of quantity requirement and you have less of it, it is called deficit in English. The opposite is called surplus or excess.

Instead of the flood of your offensive and questioning comments, a single sentence saying that the proposed constants are ambiguous would have been plenty enough. Then my answer answer would have simply been "You are right".

In fact, I noticed this problem and called for better names in my very first comment.

[Peter Kovacs]

Replying to alpar:

The "common sense" gives a good example for this. If you have any kind of quantity requirement and you have less of it, it is called deficit in English. The opposite is called surplus or excess.

It is only one point of view. The supply parameter of the MCF problem can be viewed as something you already have at the nodes, as well as a requirement. The first one is at least as logical (according to the meaning of supply). Moreover the OUT-IN < SUPPLY case doesn't mean that you cannot carry out more (so you have deficit), it rather means that you need not carry out more (if the soultion is reached), but in many cases you could.

Instead of the flood of your offensive and questioning comments, a single sentence saying that the proposed constants are ambiguous would have been plenty enough. Then my answer answer would have simply been "You are right".

You said "You are definitely wrong here", that is what I answered to. "A single sentence saying that the proposed constants are ambiguous would have been plenty enough" form you, too. I wasn't more offensive than you. I said "I think you are worng here" in reply to your "You are definitely wrong here" sentence.

In fact, I noticed this problem and called for better names in my very first comment.

It seems that these notions are used consistently related to flow problems and algorithms, that is what I wanted to proove. However I willingly accept your point of view, that it could be misleading for some users.

What about the following names?

• SATISFY_DEMANDS for the OUT-IN <= SUPPLY case
• SATISFY_SUPPLIES for the OUT-IN >= SUPPLY case
• SATISFY_ALL for the OUT-IN = SUPPLY case

I think notions supply and demand (and supply nodes, demand nodes) are more clear than excess and deficit.

Another reason for using these names is that NetworkSimplex would provide such soultion for the SATISFY_DEMANDS case in which we have equality at the demand nodes, and such soultion for the SATISFY_SUPPLIES case in which we have equality at the supply nodes (unless there are arcs with negative costs).

[Alpar Juttner]

Replying to kpeter:

Replying to alpar:

The "common sense" gives a good example for this. If you have any kind of quantity requirement and you have less of it, it is called deficit in English. The opposite is called surplus or excess.

It is only one point of view. [...longish blalba...]

Stop this, please.

[Alpar Juttner]

Replying to kpeter:

What about the following names?

• SATISFY_DEMANDS for the OUT-IN <= SUPPLY case

Acceptable.

• SATISFY_SUPPLIES for the OUT-IN >= SUPPLY case

A bit strange. A supply don't have to be 'satisfied' but rather 'used' of 'exhausted' or so.

• SATISFY_ALL for the OUT-IN = SUPPLY case

What about using LEQ and GEQ? This refers to the math formalization in the doc, so it is certainly unambiguous, though a bit abstract.

[Peter Kovacs]

Replying to alpar:

Replying to kpeter:

What about the following names?

• SATISFY_DEMANDS for the OUT-IN <= SUPPLY case

Acceptable.

• SATISFY_SUPPLIES for the OUT-IN >= SUPPLY case

A bit strange. A supply don't have to be 'satisfied' but rather 'used' of 'exhausted' or so.

Yes, but it seemed better to use the same word in both names. (Btw. this direction of the inequalities doesn't seem less strange for me than the name SATISFY_SUPPLIES.)

• SATISFY_ALL for the OUT-IN = SUPPLY case

What about using LEQ and GEQ? This refers to the math formalization in the doc, so it is certainly unambiguous, though a bit abstract.

I also thought about it, but I do not like it, since it heavily depends on what we have on the left side and what we have on the right side of the inequalities (it could be a matter of taste although in LP formulations this form is typical). A user have to check the doc in order to be sure in the usage of these names, doesn't (s)he?

[Alpar Juttner]

From the const names above, I still prefer LEQ/GEQ. I admit, it is not very brilliant name, but at least their meaning is out of question.

So - unless anyone has a better suggestion - I suggest using it.

[Peter Kovacs]

Replying to alpar:

From the const names above, I still prefer LEQ/GEQ. I admit, it is not very brilliant name, but at least their meaning is out of question.

So - unless anyone has a better suggestion - I suggest using it.

I had a suggestion, that I find better, since it says something about the real meaning of of these two cases and not depend on the actual formulation, which could be a matter of taste. Using LEQ and GEQ it seems to be (much) more diffuclt to memorize which one is which. In a (real world) application notions like 'supply' and 'demand' have clear meanings, but there isn't any LEQ or GEQ.

Another question, which is much more important: I definitely suggest using three sates (if we use more than one), so EQ, LEQ, GEQ, and I want EQ to be the default. As well as in Circulation. In that class we should introduce two cases EQ and GEQ, and we could also support LEQ in the future.

[Peter Kovacs]

Replying to kpeter:

I had a suggestion, that I find better, since it says something about the real meaning of of these two cases and not depend on the actual formulation, which could be a matter of taste. Using LEQ and GEQ it seems to be (much) more diffuclt to memorize which one is which. In a (real world) application notions like 'supply' and 'demand' have clear meanings, but there isn't any LEQ or GEQ.

After some personal discussions I am going to accept using LEQ, GEQ (and EQ).
(Maybe the other constants could also be introduced as an alias.)

Another question, which is much more important: I definitely suggest using three sates (if we use more than one), so EQ, LEQ, GEQ, and I want EQ to be the default. As well as in Circulation. In that class we should introduce two cases EQ and GEQ, and we could also support LEQ in the future.

As far as I know the main reason agianst this suggestion was the additional running time that would be needed in Circulation. However I think it wouldn't result in a notable difference compared with other parts of the algorithm or even the initialization process (creating and initializing maps). Moreover it could help discover unfeasibility earlier in some cases.

So three options can be considered:

1. Use EQ as default for Circulation and MCF classes as well.
2. Use GEQ as default for Circulation and EQ for MCF classes.
3. Use GEQ as default for Circulation and MCF classes as well.

Now I sligthly prefer the first one, but I could accept the second one if there is a good reason for that. However I definitely don't like the third option, especially because the EQ form is the widely used and known form of the MCF problem, and the GEQ form cannot be supported by some algorithms, e.g. cycle canceling algorithms (without copying and extending the graph).

Could you tell me which option do you like and why?

[Alpar Juttner]

Replying to kpeter:

Replying to kpeter: Could you tell me which option do you like and why?

There is another option which I prefer:

4. There is no EQ enum for the problemType() et all. Each algorithm use GEQ by default, except for the cycle canceling algorithm, which can only handle the EQ form so changes are not possible. (These latter algorithm isn't of practical use, anyway).

This choice is simpler than the other three but still gives the same functionality.

However, if simplicity is strongly irritating for "the community", I can also accept choice 1. :)

[Peter Kovacs]

Replying to alpar:

There is another option which I prefer:

4. There is no EQ enum for the problemType() et all. Each algorithm use GEQ by default, except for the cycle canceling algorithm, which can only handle the EQ form so changes are not possible. (These latter algorithm isn't of practical use, anyway).

In fact, it is a special case of option 3.

This choice is simpler than the other three but still gives the same functionality.

It is matter of taste, which one is simplier. It would be different from (almost) all the other MCF defintions used in network flows theory, and IMHO it would be more difficult to understand for those, who haven't known this problem before, too. (Probably not for mathematicians. :))

However, if simplicity is strongly irritating for "the community", I can also accept choice 1. :)

:) Agreed!

[Alpar Juttner]

Replying to kpeter:

Replying to alpar:

There is another option which I prefer:

4. There is no EQ enum for the problemType() et all. Each algorithm use GEQ by default, except for the cycle canceling algorithm, which can only handle the EQ form so changes are not possible. (These latter algorithm isn't of practical use, anyway).

In fact, it is a special case of option 3.

This choice is simpler than the other three but still gives the same functionality.

It is matter of taste, which one is simplier.

For the vast majority, two choices are less than three.

It would be different from (almost) all the other MCF defintions used in network flows theory.

Not exactly. The GEQ form is a generalization of the "usual" EQ one. Therefore, the GEQ formulation is the same for the problems that are feasible input of the "usual" EQ version.

and IMHO it would be more difficult to understand for those, who haven't known this problem before, too.

A single sentence in the doc saying that GEQ form and EQ form are the same for problems where supply=demand should fully eliminate this problem.

[Balazs Dezso]

I think, the equality type is not necessary, so we can remove it.

However, I disapprove the EQ/LEQ/GEQ names, the abbreviations of equal/less-or-equal/greater-or-equal are used differently in several languages:

• Fortran EQ/LE/GE
• bash eq/le/ge
• latex =/leq/geq
• assembly je/jle(jng)/jge(jnl)

I support rather long names with shortcuts:

enum ProblemType {
  EQUAL,
  GREATER_OR_EQUAL,
  LESS_OR_EQUAL,
  EQ = EQUAL,
  GE = GREATER_OR_EQUAL,
  LE = LESS_OR_EQUAL,
  GEQ = GREATER_OR_EQUAL,
  LEQ = LESS_OR_EQUAL
};

But, the equality is not necessary.

[Alpar Juttner]

Replying to deba:

I think, the equality type is not necessary, so we can remove it.

However, I disapprove the EQ/LEQ/GEQ names, the abbreviations of equal/less-or-equal/greater-or-equal are used differently in several languages:

• Fortran EQ/LE/GE
• bash eq/le/ge
• latex =/leq/geq
• assembly je/jle(jng)/jge(jnl)

I support rather long names with shortcuts:

enum ProblemType {
  EQUAL,
  GREATER_OR_EQUAL,
  LESS_OR_EQUAL,
  EQ = EQUAL,
  GE = GREATER_OR_EQUAL,
  LE = LESS_OR_EQUAL,
  GEQ = GREATER_OR_EQUAL,
  LEQ = LESS_OR_EQUAL
};

I don't think we need this mess. GEQ/LEQ/EQ is just alright IMHO. EQ/LE/GE is also an option but not better at all. I know there still exist some exotic people using FORTRAN, but I guess LaTeX is the most widespread language in our targeted audience amongst your examples.

But, the equality is not necessary.

We probably have no choice here. The EQ option is so close to Peter's heart, that it will be there however we argue.

Anyway, these whole min cost flow staff would not exist without his hard work. Thus we must come around to his way of thinking.

[Alpar Juttner]

Replying to alpar:

We probably have no choice here. The EQ option is so close to Peter's heart, that it will be there however we argue.

I intended to put a smiley here.

[Peter Kovacs]

Replying to alpar:

I don't think we need this mess. GEQ/LEQ/EQ is just alright IMHO.

I agree. I dislike GREATER_OR_EQUAL and LESS_OR_EQUAL. Maybe LE and GE could be supported as an alternative, but I don't find them really important.

EQ/LE/GE is also an option but not better at all. I know there still exist some exotic people using FORTRAN, but I guess LaTeX is the most widespread language in our targeted audience amongst your examples.

But, the equality is not necessary.

It doesn't seem good to have EQ as an option unless it is the default.

We probably have no choice here. The EQ option is so close to Peter's heart, that it will be there however we argue.

Theoretically I can be convinced, but it isn't so easy. :) However it is much easier to vote me down... :))

I intended to put a smiley here.

Here it is: :)

Anyway, these whole min cost flow staff would not exist without his hard work.

Thank you very much.

Thus we must come around to his way of thinking.

Not necessarily.

Let's summerize what we argued.

1. Constant names. GEQ, LEQ are accepted. Maybe alias names could be introduced as well. In fact, I would be happy to have SATISFY_DEMANDS and CARRY_SUPPLIES or PUSH_SUPPLIES (or something similar) as well.

2. Circulation. I accept that only the GEQ form is supported wihout any option to change it (current state). However checking the sign of the total supply at the beginning of the init() function is still worth considering. It could help discover unfeasibility earlier in some trivial cases, but is unnecessary for inputs that have feasible solution.

3. MCF classes. Cycle Canceling algorithms can support only the EQ form, but the other algorithms could be modified to support the GEQ form relatively easily (as far as I see). So the EQ form couldn't be totally disregarded. Thus the default behavior of NetworkSimplex, CapacityScaling and CostScaling will be different form CycleCanceling (and CancelAndTighten in the future) or different from Circulation (if we agree in point 2.). So that is what we have to decide. I've just supported EQ as default to ensure uniform and maybe simplier default behavior for all algorithms. However if you don't find these reasons so important, I could accept the other choice.

[Peter Kovacs]

[e6927fe719e] solves all these issues.

• NetworkSimplex class:
  • By defualt the GEQ form is supported instead of the equality form (as in Circulation).
  • enum ProblemType and a function problemType() are added to change between GEQ and LEQ options.
  • The test file is extended with test cases for both inequality forms.
  • The documentation is also improved.

• Min. cost flow module documentation:
  • The min. cost flow problem is defined in the GEQ form.
  • There are notes about the suggestive meaning of the formulation, as well.
  • There are notes about the LEQ form, too, and the way how it can be transformed into the GEQ form.
  • There are notes about the dual solution and the optimality conditions. I have never read about the optimality conditions of this inequality form, so I had to guess a suitable one. It seems to be all right, but I kindly ask you to check it.

[Peter Kovacs]

Replying to alpar:

We probably have no choice here. The EQ option is so close to Peter's heart, that it will be there however we argue.

As you can see it won't. So you have won. :))

In return please check the interface and the documentation of NetworkSimplex, as well as the module documentation. Thank you.

[Alpar Juttner]

Replying to kpeter:

In return please check the interface and the documentation of NetworkSimplex, as well as the module documentation. Thank you.

Done.

It might be good the support this choice in dimacs_solver, too. Namely, it could check the sum of supplies and report on stdout if it is negative, zero or positive and which problem type is going to be solved.

[Peter Kovacs]

The [19b6f20e0ea2] contains the required changes. It was attached (as part of a bundle file) to #234.

[Peter Kovacs]

In fact, another question has arisen about dimacs-solver. An output file can be given to it, but it is never used. All output is printed to cerr.

I suggest removing the output file parameter and use cout instead of cerr.

[Alpar Juttner]

Replying to kpeter:

In fact, another question has arisen about dimacs-solver. An output file can be given to it, but it is never used. All output is printed to cerr.

Because printing the output has not implemented yet. Are there "commonly accepted" DIMACS output file formats?

[Peter Kovacs]

Replying to alpar:

Because printing the output has not implemented yet. Are there "commonly accepted" DIMACS output file formats?

I only found performance report and correctness checking file formats, but neither of them is what we actually need.

So I suggest a note for the output file parameter saying that it is not used yet. And after that we could close this ticket.

[Alpar Juttner]

Replying to kpeter:

Replying to alpar:

Because printing the output has not implemented yet. Are there "commonly accepted" DIMACS output file formats?

I only found performance report and correctness checking file formats, but neither of them is what we actually need.

Why? I think both are natural and useful output, provided that they are in some "widely accepted" format.

So I suggest a note for the output file parameter saying that it is not used yet. And after that we could close this ticket.

Agreed.

[Peter Kovacs]

Replying to alpar:

Why? I think both are natural and useful output, provided that they are in some "widely accepted" format.

I've created a new ticket about it, see #271.