Source
IntegralFlowHomologousArcs (to be implemented — see issue #292)
Target
ILP/i32
Motivation
Enables ILP-based solving for IntegralFlowHomologousArcs. The problem's constraints — capacity bounds, flow conservation, homologous arc equality, and flow requirement — are all linear over integer variables. The reduction is a direct transcription of the problem definition into an ILP instance, requiring no gadgets or structural transformation.
Reference
Standard ILP formulation of a constrained network flow problem. No specific paper needed.
Reduction Algorithm
Given an instance of IntegralFlowHomologousArcs with directed graph G = (V, A), source s, sink t, capacities c(a) ∈ Z⁺ for each arc a, requirement R ∈ Z⁺, and homologous pairs H ⊆ A × A.
Let |A| = m, |V| = n, |H| = h.
Step 1: Create variables. One integer variable xᵢ for each arc aᵢ ∈ A (i = 0, …, m−1).
Step 2: Capacity constraints. For each arc aᵢ:
This gives m constraints. (Lower bounds xᵢ ≥ 0 are handled by the ILP variable domain.)
Step 3: Conservation constraints. For each vertex v ∈ V \ {s, t}, let δ⁻(v) be the set of incoming arcs and δ⁺(v) be the set of outgoing arcs. The conservation equality:
Σ_{aᵢ ∈ δ⁻(v)} xᵢ − Σ_{aᵢ ∈ δ⁺(v)} xᵢ = 0
Each equality is encoded as two linear inequalities (≤ 0 and ≥ 0). This gives 2(n − 2) constraints.
Step 4: Homologous constraints. For each pair (aᵢ, aⱼ) ∈ H:
xᵢ − xⱼ = 0
Each equality is encoded as two inequalities. This gives 2h constraints.
Step 5: Requirement constraint. Let δ⁻(t) be the arcs incoming to the sink:
Σ_{aᵢ ∈ δ⁻(t)} xᵢ ≥ R
This gives 1 constraint.
Step 6: Objective. Set a trivial objective: minimize 0 (empty objective vector, minimize sense). Since IntegralFlowHomologousArcs is a satisfaction problem, we only need feasibility — any solution to the ILP is a valid flow assignment.
Correctness Argument
The mapping is a bijection between feasible flows and feasible ILP solutions:
(⇒) A feasible flow f satisfying all four conditions (capacity, conservation, homologous equality, requirement) directly satisfies all ILP constraints by construction — each constraint encodes one of these conditions.
(⇐) Any feasible ILP solution x defines a flow f(aᵢ) = xᵢ that satisfies capacity (Step 2), conservation (Step 3), homologous equality (Step 4), and the requirement (Step 5).
No auxiliary variables are introduced; the correspondence is one-to-one.
Size Overhead
| Target metric |
Formula |
num_vars |
num_arcs |
num_constraints |
num_arcs + 2 * num_vertices + 2 * num_homologous_pairs - 3 |
Derivation: m capacity + 2(n−2) conservation + 2h homologous + 1 requirement = m + 2n + 2h − 3.
Validation Method
Closed-loop test: construct a small source instance, reduce to ILP, solve the ILP, extract the solution back as a flow assignment, and verify it satisfies all original constraints.
Example Instance
Source: 6 vertices {0=s, 1, 2, 3, 4, 5=t}, 8 arcs (all unit capacity):
- a₀=(0,1), a₁=(0,2), a₂=(1,3), a₃=(2,3), a₄=(1,4), a₅=(2,4), a₆=(3,5), a₇=(4,5)
- H = {(a₂, a₅), (a₄, a₃)}, R = 2
Target ILP/i32: 8 variables x₀…x₇, 21 constraints:
Capacity (8): xᵢ ≤ 1 for i = 0…7
Conservation (8 = 4 vertices × 2):
- v1: x₀ − x₂ − x₄ ≤ 0 and x₀ − x₂ − x₄ ≥ 0
- v2: x₁ − x₃ − x₅ ≤ 0 and x₁ − x₃ − x₅ ≥ 0
- v3: x₂ + x₃ − x₆ ≤ 0 and x₂ + x₃ − x₆ ≥ 0
- v4: x₄ + x₅ − x₇ ≤ 0 and x₄ + x₅ − x₇ ≥ 0
Homologous (4 = 2 pairs × 2):
- x₂ − x₅ ≤ 0 and x₂ − x₅ ≥ 0
- x₄ − x₃ ≤ 0 and x₄ − x₃ ≥ 0
Requirement (1): x₆ + x₇ ≥ 2
Objective: minimize 0.
Solution: x = [1, 1, 1, 0, 0, 1, 1, 1]. Flow value = x₆ + x₇ = 2 ≥ R. All constraints satisfied. ✓
Source
IntegralFlowHomologousArcs (to be implemented — see issue #292)
Target
ILP/i32
Motivation
Enables ILP-based solving for IntegralFlowHomologousArcs. The problem's constraints — capacity bounds, flow conservation, homologous arc equality, and flow requirement — are all linear over integer variables. The reduction is a direct transcription of the problem definition into an ILP instance, requiring no gadgets or structural transformation.
Reference
Standard ILP formulation of a constrained network flow problem. No specific paper needed.
Reduction Algorithm
Given an instance of IntegralFlowHomologousArcs with directed graph G = (V, A), source s, sink t, capacities c(a) ∈ Z⁺ for each arc a, requirement R ∈ Z⁺, and homologous pairs H ⊆ A × A.
Let |A| = m, |V| = n, |H| = h.
Step 1: Create variables. One integer variable xᵢ for each arc aᵢ ∈ A (i = 0, …, m−1).
Step 2: Capacity constraints. For each arc aᵢ:
This gives m constraints. (Lower bounds xᵢ ≥ 0 are handled by the ILP variable domain.)
Step 3: Conservation constraints. For each vertex v ∈ V \ {s, t}, let δ⁻(v) be the set of incoming arcs and δ⁺(v) be the set of outgoing arcs. The conservation equality:
Σ_{aᵢ ∈ δ⁻(v)} xᵢ − Σ_{aᵢ ∈ δ⁺(v)} xᵢ = 0
Each equality is encoded as two linear inequalities (≤ 0 and ≥ 0). This gives 2(n − 2) constraints.
Step 4: Homologous constraints. For each pair (aᵢ, aⱼ) ∈ H:
xᵢ − xⱼ = 0
Each equality is encoded as two inequalities. This gives 2h constraints.
Step 5: Requirement constraint. Let δ⁻(t) be the arcs incoming to the sink:
Σ_{aᵢ ∈ δ⁻(t)} xᵢ ≥ R
This gives 1 constraint.
Step 6: Objective. Set a trivial objective: minimize 0 (empty objective vector, minimize sense). Since IntegralFlowHomologousArcs is a satisfaction problem, we only need feasibility — any solution to the ILP is a valid flow assignment.
Correctness Argument
The mapping is a bijection between feasible flows and feasible ILP solutions:
(⇒) A feasible flow f satisfying all four conditions (capacity, conservation, homologous equality, requirement) directly satisfies all ILP constraints by construction — each constraint encodes one of these conditions.
(⇐) Any feasible ILP solution x defines a flow f(aᵢ) = xᵢ that satisfies capacity (Step 2), conservation (Step 3), homologous equality (Step 4), and the requirement (Step 5).
No auxiliary variables are introduced; the correspondence is one-to-one.
Size Overhead
num_varsnum_arcsnum_constraintsnum_arcs + 2 * num_vertices + 2 * num_homologous_pairs - 3Derivation: m capacity + 2(n−2) conservation + 2h homologous + 1 requirement = m + 2n + 2h − 3.
Validation Method
Closed-loop test: construct a small source instance, reduce to ILP, solve the ILP, extract the solution back as a flow assignment, and verify it satisfies all original constraints.
Example Instance
Source: 6 vertices {0=s, 1, 2, 3, 4, 5=t}, 8 arcs (all unit capacity):
Target ILP/i32: 8 variables x₀…x₇, 21 constraints:
Capacity (8): xᵢ ≤ 1 for i = 0…7
Conservation (8 = 4 vertices × 2):
Homologous (4 = 2 pairs × 2):
Requirement (1): x₆ + x₇ ≥ 2
Objective: minimize 0.
Solution: x = [1, 1, 1, 0, 0, 1, 1, 1]. Flow value = x₆ + x₇ = 2 ≥ R. All constraints satisfied. ✓