Lower bounds

1 Problem framing: generalized circulation with lower bounds

1.1 Directed network and arc-flow variables

A generalized circulation problem is posed on a directed graph \(G=(V,E)\). For each arc \((i,j)\in E\), the model introduces a continuous or integer flow variable \(x_{ij}\) representing the amount sent from node \(i\) to node \(j\). In a circulation setting, flows are constrained to satisfy balance requirements at nodes, with possible external demand or supply terms.

1.2 Flow conservation and demand balance

Flow conservation enforces that the total inflow and outflow at each node are related by a balance equation. A common form uses node net supply/demand values \(b_i\), where the convention is that positive \(b_i\) indicates net supply and negative \(b_i\) indicates net demand. The conservation rule can be written as: \[ \sum_{j:(i,j)\in E} x_{ij} - \sum_{j:(j,i)\in E} x_{ji} = b_i \quad \forall i\in V. \] When all \(b_i=0\), the instance is a pure circulation; otherwise, it is a circulation with demands.

1.3 Lower-bound constraints as minimum arc throughput

Each arc \((i,j)\) may be required to carry at least some minimum throughput. This appears as a lower bound: \[ x_{ij} \ge \ell_{ij}. \] Such constraints model situations where an arc must be used to meet service levels, minimum shipping commitments, routing reservations, or minimum processing volumes.

1.4 Relationship to upper bounds and capacity intervals

Lower bounds are often paired with upper bounds: \[ \ell_{ij} \le x_{ij} \le u_{ij}, \] where \(u_{ij}\) denotes a capacity limit. The feasible set for each arc is then an interval \([\ell_{ij},u_{ij}]\), provided \(\ell_{ij}\le u_{ij}\). Feasibility and optimization depend on how these intervals interact with node balances.

2 Mathematical formulation

2.1 Standard lower/upper bounded flow model

2.1.1 Variable definitions for each arc

The canonical formulation uses one variable per directed arc. Let \(x_{ij}\) denote the flow on arc \((i,j)\). The model may allow real-valued flows (fractional) or restrict them to integers, depending on the application.

2.1.2 Inequality and equality constraints

A standard linear programming representation is: \[ \ell_{ij} \le x_{ij} \le u_{ij} \quad \forall (i,j)\in E, \] together with node balance constraints: \[ \sum_{j} x_{ij} - \sum_{j} x_{ji} = b_i \quad \forall i\in V, \] where the sums are taken over outgoing and incoming arcs, respectively. Additional constraints can encode integrality, but the core structure is governed by these bounds and equalities.

2.2 Feasibility vs. optimization objectives

Some generalized circulation problems focus solely on feasibility—deciding whether there exists any flow satisfying the bounds and balances. Others incorporate objective functions, such as minimizing cost, maximizing throughput, or optimizing a secondary criterion, while still respecting all lower-bound requirements.

2.3 Objective functions compatible with lower bounds

Because lower bounds simply restrict the feasible region, many objective functions remain valid after imposing them. Typical examples include linear costs \( \sum_{(i,j)\in E} c_{ij}x_{ij}\) or piecewise-linear penalties. When costs are linear and bounds are intervals, the resulting model remains a linear program with the same conservation structure.

3 Transformations to remove lower bounds

3.1 Lower-bound substitution (residual capacity shift)

A common technique eliminates lower bounds by shifting variables. Define: \[ y_{ij} = x_{ij} - \ell_{ij}. \] Then \(y_{ij}\ge 0\), and the upper bound transforms into: \[ y_{ij} \le u_{ij}-\ell_{ij} \equiv \bar{u}_{ij}. \] This converts each arc’s constraint from a lower-bounded interval to a nonnegative variable with an adjusted capacity.

3.2 Node-balance adjustment induced by lower bounds

Substituting \(x_{ij}=\ell_{ij}+y_{ij}\) into the balance equation modifies the right-hand side. The balance becomes: \[ \sum_{j} (\ell_{ij}+y_{ij}) - \sum_{j} (\ell_{ji}+y_{ji}) = b_i. \] Rearranging yields: \[ \sum_{j} y_{ij} - \sum_{j} y_{ji} = b_i - \left(\sum_{j}\ell_{ij}-\sum_{j}\ell_{ji}\right). \] Thus, lower bounds contribute a fixed net flow that can be absorbed into adjusted node supplies/demands.

3.3 Equivalent circulation formulation

After the substitution, the model becomes a standard circulation (or circulation with demands) in terms of \(y\), with only nonnegativity and upper limits. The conservation constraints remain equalities, but the node imbalance vector is shifted to reflect the lower-bound flow that is “baked into” the transformation.

3.4 Constructing the transformed network

To construct the equivalent instance:

1. Replace each arc \((i,j)\) capacity \(u_{ij}\) with residual capacity \(\bar{u}_{ij}=u_{ij}-\ell_{ij}\).
2. Replace each node balance value \(b_i\) with adjusted balance:

\[ b'_i = b_i - \left(\sum_{j}\ell_{ij}-\sum_{j}\ell_{ji}\right). \]

1. Solve for nonnegative flows \(y_{ij}\) satisfying \(\sum_j y_{ij}-\sum_j y_{ji}=b'_i\) and \(0\le y_{ij}\le \bar{u}_{ij}\).

Finally, recover the original flows by \(x_{ij}=\ell_{ij}+y_{ij}\).

4 Feasibility conditions

4.1 Necessary and sufficient criteria via transformed supplies/demands

Feasibility depends on whether the transformed demand vector \(b'\) can be satisfied within the adjusted arc capacities \(\bar{u}_{ij}\). In linear programming terms, feasibility holds if the transformed flow polytope is nonempty. In classical network-flow theory, such feasibility can be checked by converting the instance into a circulation feasibility test with added structures.

4.2 Cut-based intuition (capacity across network partitions)

A useful intuition uses cuts. Consider partitioning nodes into two sets \(S\) and \(V\setminus S\). Net flow leaving \(S\) through arcs crossing the cut is limited by the total capacity of those crossing arcs. Meanwhile, the balance equations impose a required net outflow determined by \(\sum_{i\in S} b'_i\). Infeasibility emerges when required net flow exceeds what the cut can transmit.

4.3 Checking feasibility with flow algorithms

Practical checks reduce feasibility to running a maximum-flow algorithm on a constructed auxiliary network. Common approaches introduce a super-source and super-sink to satisfy positive and negative components of \(b'\), then test whether all demand can be met up to capacity constraints. If the algorithm saturates the required connections, the original lower-bounded instance is feasible.

4.4 Detecting infeasibility and interpreting violations

If feasibility fails, the auxiliary algorithm typically produces a cut or residual structure indicating where capacity is insufficient. Interpreting such certificates in terms of the original model helps explain which lower bounds cannot simultaneously be honored with the conservation rules and available capacities. In optimization settings, infeasibility may also be detected indirectly via dual variables or constraint violations returned by solvers.

5 Algorithmic approaches

5.1 Reduction to circulation with demands

After shifting by lower bounds, one obtains an instance where \(y\) satisfies standard conservation with adjusted node demands \(b'\). The problem then aligns with known circulation feasibility and optimization algorithms, such as those based on min-cost circulation or max-flow reductions depending on the objective.

5.2 Reduction to max-flow/min-cut subroutines

For feasibility, the model is often reduced to a max-flow computation:

1. Compute \(b'\).
2. Add a super-source connected to nodes with \(b'_i>0\) with edge capacity \(b'_i\).
3. Add a super-sink connected from nodes with \(b'_i<0\) with capacity \(-b'_i\).
4. Keep original residual-capacity arcs \(y_{ij}\) with capacities \(\bar{u}_{ij}\).

Then a maximum flow is computed; feasibility holds if all supply from the super-source can reach the super-sink.

5.3 Complexity considerations and implementation notes

The computational complexity depends on the graph size and the algorithm used for max-flow or min-cost circulation. Implementations must carefully handle:

• arcs with \(\bar{u}_{ij}=0\),
• feasibility when \(b'\) does not sum to zero (an immediate inconsistency for a pure circulation balance),
• numerical stability for continuous solvers,
• integrality requirements if integer flows are required (which may necessitate integral-capacity conditions and appropriate algorithms).

5.4 Handling both lower and upper bounds simultaneously

The transformation naturally accommodates both types of bounds: upper limits become residual capacities, and lower limits shift node balances. Algorithms then proceed exactly as for ordinary circulation with capacity upper bounds, using \(\bar{u}_{ij}=u_{ij}-\ell_{ij}\) and \(b'\) as the adjusted demand/supply.

6 Special cases and variants

6.1 Exact lower bounds (minimum equals maximum on an arc)

If an arc has \(\ell_{ij}=u_{ij}\), then its flow is fixed: \(x_{ij}\) must equal that exact value. In the shifted model, the residual capacity \(\bar{u}_{ij}=0\), so \(y_{ij}=0\) and the fixed flow contributes deterministically to the node balance adjustment. This can simplify feasibility checking by effectively contracting or removing fixed arcs while updating \(b&#039;\).

6.2 No upper bounds on certain arcs

When an arc has no upper constraint, it can be represented by a sufficiently large upper bound in continuous settings, or by treating it as having infinite capacity. In the transformed model, \(\bar{u}_{ij}\) becomes infinite as well, meaning that arc cannot be the limiting factor for feasibility. However, unboundedness in costed problems still requires care.

6.3 Only lower bounds with strict conservation

If there are only lower bounds (and possibly no meaningful upper bounds) but strict node conservation holds, feasibility becomes mainly about whether the fixed contributions implied by \(\ell_{ij}\) can be balanced by the remaining flexible arcs. The transformation still works: the adjusted demands \(b'\) may force certain net transfer patterns that the unlimited-capacity arcs must support.

6.4 Arc subsets with mandatory flow

Sometimes lower bounds apply only to a subset of arcs, reflecting mandatory usage (e.g., reserved lanes, guaranteed connections, or compulsory processing steps). Then \(\ell_{ij}=0\) for other arcs, so only those mandatory arcs shift node balances. The rest of the network then provides flexibility within their capacities to satisfy the modified conservation equations.

7 Generalized circulation extensions

7.1 Multi-commodity considerations (conceptual overview)

In multi-commodity flow problems, multiple distinct flow types share network structure and may compete on capacities. Lower bounds can be imposed per commodity or on aggregated usage. While feasibility transformations for single-commodity lower-bounded circulation extend only partially, the same conceptual shift—treating minimum requirements as fixed contributions—often inspires modeling approaches, though exact polynomial reductions are more complex.

7.2 Time-expanded networks with lower bounds

Time-expanded formulations replicate nodes and arcs across time steps to represent dynamic behavior. Lower bounds can then encode minimum service or minimum throughput per time layer. After shifting, residual capacities and adjusted node balances occur at each time-expanded node, preserving the conservation logic but enlarging the graph.

7.3 Lower bounds in bipartite and assignment-like structures

Bipartite flow models represent matching or assignment using capacities on arcs between left and right node sets. Lower bounds can require that certain pairs or groups receive at least a minimum number of units, producing “quota” assignment variants. Even though the underlying structure is bipartite, feasibility and reduction techniques still rely on the same lower-bound shift and circulation logic when interpreted as a flow network.

7.4 Coupled constraints beyond simple arc minima (overview)

Some models include dependencies such as “if arc \(a\) is used then arc \(b\) must also carry a minimum,” or group-based quotas across sets of arcs. These couplings go beyond independent per-arc minima and may not admit a simple lower-bound removal. Nevertheless, the foundational idea of transforming bounds into adjusted balances can remain useful for the portions of the model that are separable.

8 Applications and modeling patterns

8.1 Minimum throughput requirements in routing systems

In routing and logistics, lower-bounded arcs represent minimum routing commitments along certain paths or links. They may reflect guaranteed bandwidth reservation, contractual obligations, or minimum packet-forwarding requirements. Feasible solutions correspond to schedules that respect both conservation of traffic and link capacity limits while honoring the minimum usage rules.

8.2 Minimum service levels in scheduling networks

Scheduling networks often model tasks as flows that must traverse resource nodes. Lower bounds enforce minimum service quantities, such as ensuring that at least \(k\) units of work pass through a processing stage or that certain time slots receive a minimum allocation. The resulting circulation feasibility check can confirm whether the service-level commitments can be met given resource capacities.

8.3 Reliability/coverage analogs using minimum flows

Minimum flow requirements can serve as analogs of coverage or reliability in abstract networked systems: each route segment might need a minimum level of traffic to represent redundancy, monitoring presence, or coverage targets. Though real reliability modeling can be more nuanced, lower-bounded circulation provides a tractable way to encode deterministic minimum coverage.

8.4 Interpreting solutions in the original units

After solving the transformed problem, the solution must be translated back to the original flows via \(x_{ij}=\ell_{ij}+y_{ij}\). Interpretation then uses the original units (bandwidth, jobs, vehicles, or time-slot allocations), ensuring that the fixed minimum contributions and the additional “residual” allocation combine to meet the node balance requirements.

9 Worked examples (conceptual workflows)

9.1 Transforming a small lower-bounded circulation instance

Consider a directed graph with a few nodes and arcs, where each arc has a lower bound \(\ell_{ij}\) and an upper bound \(u_{ij}\). The workflow is:

• Shift variables to \(y_{ij}=x_{ij}-\ell_{ij}\).
• Compute residual capacities \(\bar{u}_{ij}=u_{ij}-\ell_{ij}\).
• Adjust each node’s balance \(b'_i=b_i-\left(\sum_j\ell_{ij}-\sum_j\ell_{ji}\right)\).

The transformed instance becomes a standard circulation with demands using only nonnegative variables \(y\).

9.2 Computing node imbalances and verifying feasibility

Next, compute the net positive and negative parts of \(b&#039;\). The reduction introduces a super-source connected to nodes with \(b&#039;_i&gt;0\) (capacity \(b&#039;_i\)) and a super-sink connected from nodes with \(b&#039;_i&lt;0\) (capacity \(-b&#039;_i\)). Running max-flow determines whether all supply can be routed through residual-capacity arcs.

9.3 Recovering original arc flows from the transformed solution

If the transformed solution provides values \(y_{ij}\), reconstruct original flows by adding back the minima: \(x_{ij}=\ell_{ij}+y_{ij}\). Verification steps include checking original inequalities \(\ell_{ij}\le x_{ij}\le u_{ij}\) and confirming that original node balances \(\sum_j x_{ij}-\sum_j x_{ji}=b_i\) hold.

9.4 Common pitfalls in manual reductions

Typical mistakes include:

• updating \(b_i\) with incorrect sign convention (using inflow minus outflow instead of outflow minus inflow),
• forgetting to subtract \(\ell_{ij}\) from \(u_{ij}\) when forming residual capacities,
• misapplying feasibility conditions without ensuring that the transformed instance’s demands are consistent with total flow balance,
• reconstructing \(x\) but failing to re-check bounds.

10 Theoretical properties

10.1 Existence of feasible circulations under constraints

Feasibility of lower-bounded generalized circulation is guaranteed precisely when the transformed instance admits a flow meeting the adjusted demands within residual capacities. The underlying reason is linearity: the lower-bound shift yields an equivalent system with only standard capacity and conservation constraints, so solvability is preserved.

10.2 Structure of the solution space (feasible flow polyhedra)

The set of feasible flows forms a convex polyhedron in the continuous case. Lower bounds and upper bounds define half-spaces, and conservation equations define affine constraints. When lower bounds are present, they alter the polyhedron’s position by shifting variables and node balances, but the polyhedral nature remains.

10.3 Sensitivity to changing lower bounds

Changing a lower bound \(\ell_{ij}\) affects:

• the residual capacity \(\bar{u}_{ij}=u_{ij}-\ell_{ij}\),
• the adjusted node demands \(b'_i\) and \(b'_j\) due to the fixed net flow contribution.

As a result, feasibility may flip from feasible to infeasible, and optimal objective values (when optimized) can change monotonically only under specific objective and cost structures.

10.4 Bounds tightening and monotonicity behavior

Tightening a lower bound typically reduces available flexibility on that arc (since residual capacity shrinks) and simultaneously injects more fixed flow into the network balance. Depending on whether the fixed contribution aligns with the required node balances, the feasibility region can contract or shift substantially. In contrast, tightening upper bounds always weakens capacity, generally making feasibility less likely.