Both lower and upper supply bounds in Network simplex

[Alpar Juttner]

The idea is to extend Network Simplex so that the form of the problems are fully compatible with the one used by the LP solvers i.e.

m_l<=Ax<=m_u
l<=x<=u

[Alpar Juttner]

This is Peter's comment on lemon-user: In short, we could implement the following extensions without serious difficulties and without running time overhead:

• m_l<=Ax<=m_u support for NetworkSimplex?, even for negative or positive "infinite" values in m_l and m_u, respectively. This version is a common generalization of all other forms.
• m_l<=Ax<=m_u support for the other MCF solvers if all values in m_l is finite (upper bounds could be infinite).

In details:

The general m_l<=Ax<=m_u form can be transformed to the Ax=m form by adding a new node and several arcs to the graph (they represent the slack variables of the constraints). Basically, all min cost flow algorithms solve this equality form and any other form should be transformed to this one. Therefore, all implementations could be generalized to the m_l<=Ax<=m_u form, though it could cause some technical difficulties if we allow "infinite" values for these bounds. The major problem here is that the MCF algorithms copies the graph into an internal storage (with the required artifical node and arcs) _before_ they get the maps. (The reason for that is the support of rerunning the algorithm with modified map values but without copying the graph again.)

Currently, the MCF algorithms support the m_l<=Ax form. They all could be simply extended with support of the m_l<=Ax<=m_u form if all values in m_l remains finite (upper bounds could be infinite), since only the capacities of the artifical arcs should be modified. However, supporting negative infinity as lower bound would cause more difficulties, since it would require the modification or extension of the internal graph representation, which cannot be ensured without running time overhead, because the arcs are stored in a sorted order. NetworkSimplex? is a different case, since it uses a simpler internal graph representation, which does not require a specific order of the arcs. So the stack-like arc addition and deletion in the corresponding vectors can be performed efficiently. Btw., would we like to support the case when both bounds are infinite? This would be more difficult and somewhat slower, because it requires two artifical arcs instead of one. Another important question here is the compatible and nice extension of the current interface. NetworkSimplex? has supplyMap(map) and supplyType(type) functions (where type can be LEQ or GEQ). They can be used to specify the Ax<=m or the Ax>=m forms. Should we add a new function supplyBounds(m_l, m_u) that would override the effect of both above functions? Wouldn't it be confusing? I think, it would be better to combine supplyMap(map) and supplyType(type) into a supplyMap(map, type=GEQ) function and make supplyType() deprecated. (Other MCF classes don't have such a function.) Moreover, the dual solution of the problem should also be generalized. Additional conditions:

• If OUT(i)-IN(i)<m_u(i), then p(i)<=0.
• If OUT(i)-IN(i)>m_l(i), then p(i)>=0.

Where p(i) denotes the potential of i. Consequences:

• If m_l(i)<OUT(i)-IN(i)<m_u(i), then p(i)=0.
• If m_l(i)=OUT(i)-IN(i)=m_u(i), then p(i) is unrestricted in sign.

[Peter Kovacs]

[9b4e54922851] contains a preliminary implementation of this feature. Note that it requires finite lower bounds, but supports both finite and infinite upper bounds. Moreover, the dual solution is not checked in the test file.

Further tasks:

• Implement the support of infinite lower bounds in NS.
• Revise this modification of the API.
• Revise the supplyMap() + supplyType() soluiton of NS.
• Extend the doc with this general formulation and its dual solution.
• Extend the test file with the correct checking of the dual solution for this case.
• Implement lower-upper bound support for the other MCF algorithms.

I think, it would be much better to remove the LEQ case from the documentation, and keep only the GEQ and LEQ-GEQ formulations with correct notes about their connections: GEQ is a specialized version of the LEQ-GEQ (all upper bounds are infinite) and EQ is a specialized version of GEQ. Moreover, I would like to remove the LEQ support from NS, or at least make it deprecated.

[Peter Kovacs]

[652a613b3a6d] is a fixed version of the previous patch [9b4e54922851].

[Peter Kovacs]

The proposed solution could be made more efficient. It adds two artificial arcs for each node, but one artificial arc would be sufficient for the nodes that have equal lower and upper bounds for their supply value. (Currently, one of the two artificial arcs has 0 capacity for such nodes, thus it could be omitted.) The _search_arc_num variable should also be decreased: number of original arcs + number of nodes u for which sup_lower(u) != sup_upper(u) would be sufficient. This modification could speed up the algorithm, because less arcs would be checked (priced) in each iteration.