[Rule] MinimumGraphBandwidth to ILP

[QingyunQian]

Source: MinimumGraphBandwidth
Target: ILP
Motivation: Enables exact solving of MinimumGraphBandwidth using mature ILP solvers. The minimax objective is naturally linearized via a bottleneck variable.
Reference:

• Caprara, A. & Salazar-González, J. J. (2005). "Laying out sparse graphs with provably minimum bandwidth." INFORMS J. Comput., 17(3), 356–373.

Reduction Algorithm

Notation:

• Source: MinimumGraphBandwidth instance with graph G = (V, E), n = num_vertices, m = num_edges
• Target: ILP instance with n² + 1 variables and 2n + 2m constraints

Variable mapping:

• Binary assignment variables: x_{i,p} ∈ {0, 1} for i ∈ V, p ∈ {0, ..., n−1}. x_{i,p} = 1 iff vertex i is assigned to position p. Variable index: i·n + p. Bounds: lower = 0, upper = 1.
• Bottleneck variable: B ∈ {0, ..., n−1} at index n². Bounds: lower = 0, upper = n − 1.

All variables use the ILP<i32> variant — the binary assignment variables are encoded as i32 with explicit [0, 1] bounds.

Constraint/objective transformation:

1. Row constraints (each vertex gets one position):
   ∀i ∈ V: Σ_{p=0}^{n−1} x_{i,p} = 1

2. Column constraints (each position holds one vertex):
   ∀p ∈ {0, ..., n−1}: Σ_{i=0}^{n−1} x_{i,p} = 1

3. Bandwidth constraints (∀(u,v) ∈ E):
   Σ_p p·x_{u,p} − Σ_p p·x_{v,p} ≤ B
   Σ_p p·x_{v,p} − Σ_p p·x_{u,p} ≤ B

Objective: Minimize B.

Solution extraction: From the ILP solution, read each x_{i,p} = 1 to reconstruct the vertex labeling f(i) = p. The optimal bandwidth is B.

Size Overhead

Symbols:

• n = num_vertices of source graph G
• m = num_edges of source graph G

Target metric (code name)	Polynomial (using getter names)
num_vars	num_vertices^2 + 1
num_constraints	2 * num_vertices + 2 * num_edges

Validation Method

• Cross-check with brute-force solver on small instances (n ≤ 8)
• Compare with known closed-form bandwidth values: path P_n: 1, cycle C_n: 2, grid P_r × P_c: min(r, c), star K_{1,n−1}: ⌊n/2⌋

Example

Source: P₂ × P₃ grid (2×3 grid, bandwidth = 2)

Graph:
  0 — 1 — 2
  |   |   |
  3 — 4 — 5

Vertices: {0, 1, 2, 3, 4, 5}
Edges: {(0,1), (1,2), (0,3), (1,4), (2,5), (3,4), (4,5)}
Known optimal bandwidth: 2  (Chvátalová 1975: φ(P_m × P_n) = min(m, n))

Target ILP:

Variables (37 total, all i32):
  x_{i,p} ∈ [0,1] for i,p ∈ {0..5}  (36 variables, indices 0..35)
  B ∈ [0,5]                           (1 variable, index 36)

Constraints (26 total):
  Row (6):  Σ_p x_{i,p} = 1 for each vertex i
  Col (6):  Σ_i x_{i,p} = 1 for each position p
  Bw (14):  Σ_p p·x_{u,p} − Σ_p p·x_{v,p} ≤ B  (both directions, 7 edges)

Objective: Minimize B

Solution: B = 2. Optimal column-major assignment: f(0)=0, f(3)=1, f(1)=2, f(4)=3, f(2)=4, f(5)=5.

Verification: edge spans = {|0−2|, |2−4|, |0−1|, |2−3|, |4−5|, |1−3|, |3−5|} = {2, 2, 1, 1, 1, 2, 2}, max = 2 = B ✓

Suboptimal: Row-major f(0)=0, f(1)=1, f(2)=2, f(3)=3, f(4)=4, f(5)=5 gives B = 3 (edge (0,3) spans |0−3| = 3).

Overhead: n=6, m=7 → num_vars = 37, num_constraints = 26.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	⚠️ Warn	Source problem GraphBandwidth does not yet exist in the codebase — needs a [Model] issue first
Non-trivial	✅ Pass	Assignment-based ILP with bottleneck linearization; constructs n² binary variables, row/column assignment constraints, and bandwidth-bounding constraints
Correctness	✅ Pass	Reference verified; ILP formulation is standard and mathematically sound
Well-written	✅ Pass	Complete, implementable algorithm with consistent notation and a fully worked example

Overall: 2 passed, 0 failed, 1 warning

---

Usefulness

GraphBandwidth is not currently in the reduction graph (pred show GraphBandwidth fails). This means the reduction cannot be implemented until a [Model] issue for GraphBandwidth is created and merged first. Once the model exists, no direct path GraphBandwidth → ILP will exist, so this reduction is novel and useful.

Warning: This rule depends on a model that does not yet exist. Ensure a [Model] GraphBandwidth issue is filed and implemented before this rule.

Non-trivial

The reduction is non-trivial. It constructs:

• n² binary assignment variables x_{i,p} encoding a bijection between vertices and positions
• A bottleneck integer variable B capturing the maximum edge span
• Row and column assignment constraints enforcing a valid permutation
• Bandwidth-bounding constraints linearizing the absolute difference |pos(u) - pos(v)| ≤ B for each edge

This is a genuine structural transformation from a graph ordering problem to an integer linear program, involving gadget-like linearization of a minimax objective. Not a simple variable substitution or type coercion.

Correctness

Reference verification:

• Caprara, A. & Salazar-González, J. J. (2005). "Laying out sparse graphs with provably minimum bandwidth." INFORMS Journal on Computing, 17(3), 356–373. DOI: 10.1287/ijoc.1040.0099
  • Confirmed: The paper exists. Juan-José Salazar-González's publication list at Universidad de La Laguna confirms this exact paper with matching title, journal, volume, pages, and year. The paper deals with ILP-based approaches for exact bandwidth computation.

Formulation correctness:

• The assignment-based ILP is a standard formulation for graph layout problems. Binary variables x_{i,p} encoding vertex-to-position assignment with row/column constraints is the classical approach (also related to the quadratic assignment/bottleneck assignment problem).
• The linearization of |pos(u) - pos(v)| via two inequality constraints (pos(u) - pos(v) ≤ B and pos(v) - pos(u) ≤ B) is correct and standard.
• Position values are encoded as Σ_p p·x_{i,p}, which correctly recovers the integer position from the binary assignment variables.

Validation values:

• Path P_n: bandwidth = 1 ✓ (confirmed by Wolfram MathWorld)
• Cycle C_n: bandwidth = 2 ✓ (confirmed by Wolfram MathWorld)
• Grid P_r × P_c: bandwidth = min(r,c) ✓ (confirmed by Wolfram MathWorld)
• Star K_{1,n−1}: bandwidth = ⌊n/2⌋ ✓ (confirmed by Wolfram MathWorld)

Example verification (C_5):
Assignment f(0)=0, f(1)=2, f(2)=4, f(3)=3, f(4)=1 gives edge spans {2, 2, 1, 2, 1}, max = 2 = B. ✓

Well-written

Information completeness: All required sections are present and substantive — Source, Target, Motivation, Reference, Reduction Algorithm, Size Overhead, Validation Method, and Example.

Algorithm completeness: The reduction is described as a complete, step-by-step procedure with explicit variable indexing (i·n + p for assignment variables, n² for the bottleneck variable), clearly stated constraints with mathematical formulas, and a well-defined objective.

Symbol consistency: All symbols are defined before use (n = |V|, m = |E|, i ∈ V, p ∈ {0,…,n−1}). The overhead table uses num_vars and num_constraints, which match the ILP model's size_fields.

Example quality: The C_5 example is non-trivial (5 vertices, 5 edges), fully worked (shows source instance, target ILP structure, solution, and verification), and small enough to verify by hand. The overhead calculation (n=5, m=5 → 26 vars, 20 constraints) is correct.

Recommendations

• File a [Model] GraphBandwidth issue before implementing this rule, as the source problem does not yet exist in the codebase.
• Consider whether the ILP variable B should have explicit bounds [0, n−1] documented in the algorithm section — the current description mentions the domain but the ILP constraint formulation relies on the solver inferring bounds from the binary assignment structure.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	⚠️ Warn	Source problem GraphBandwidth does not yet exist in the codebase
Non-trivial	✅ Pass	Assignment-based ILP with bottleneck linearization is a genuine structural transformation
Correctness	✅ Pass	Reference verified; ILP formulation is standard and correct
Well-written	⚠️ Warn	Minor notation issues (see below)

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

The source problem GraphBandwidth is not yet implemented in the codebase. There is no [Model] issue for it either — only rule issues (#134, #136, #137) reference it. This rule cannot be implemented until GraphBandwidth is added as a model first.

Since there is no existing path from GraphBandwidth to ILP (because GraphBandwidth does not exist), the reduction is novel. Pass on novelty, but Warn because the prerequisite model is missing.

The motivation is adequate: enabling exact solving via ILP solvers is a concrete and practical use case. The note about minimax linearization via a bottleneck variable adds substance.

Non-trivial

The reduction is non-trivial. It involves:

• Constructing n^2 binary assignment variables to encode vertex-to-position mappings
• Doubly stochastic (assignment) constraints ensuring a valid permutation
• A bottleneck variable B with 2m linearized absolute-difference constraints
• Minimax-to-linear transformation (converting min max |f(u) - f(v)| into a linear objective with auxiliary constraints)

This is a genuine gadget-based construction, not a relabeling or subtype coercion.

Correctness

Reference verification: The paper by Caprara & Salazar-Gonzalez (2005), "Laying Out Sparse Graphs with Provably Minimum Bandwidth," published in INFORMS Journal on Computing, 17(3), 356-373, was verified to exist via web search and ResearchGate. The DOI 10.1287/ijoc.1040.0099 is valid. The paper addresses the graph bandwidth problem using ILP-based approaches, which is consistent with the issue's claims.

Formulation verification: The assignment-based ILP formulation with binary position variables and a bottleneck variable is a well-known standard approach for graph bandwidth (and related quadratic bottleneck assignment problems). The formulation in the issue is mathematically correct:

• Row constraints enforce each vertex gets exactly one position
• Column constraints enforce each position is used by exactly one vertex
• Bandwidth constraints correctly linearize |pos(u) - pos(v)| <= B via two directed inequalities

Example verification: The C5 example is correct. With assignment f(0)=0, f(1)=2, f(2)=4, f(3)=3, f(4)=1, the edge spans are {2, 2, 1, 2, 1} with max = 2, which matches the known optimal bandwidth of C5.

Overhead verification: For n=5, m=5: num_vars = 26, num_constraints = 20. This matches the formulas n^2 + 1 and 2n + 2m respectively.

Well-written

Information completeness: All required sections are present and substantive (Source, Target, Motivation, Reference, Reduction Algorithm, Size Overhead, Validation Method, Example).

Algorithm completeness: The step-by-step procedure is detailed and implementable. Variable indices are explicitly defined. Constraint construction is unambiguous.

Minor issues (warnings, not failures):

1. Bottleneck variable domain: The issue states B ∈ {0, ..., n-1} but in the ILP formulation, B should be a general integer (or continuous) variable with implicit bounds from the constraints. The ILP model uses integer or continuous variables — the issue should clarify whether B is encoded as a bounded integer variable or left as a general non-negative integer. In practice, the ILP variable variant in the codebase is either bool or i32, so the implementation would need to use the i32 variant for B while keeping the x_{i,p} as bool — this mixed-variable aspect is not discussed.

2. Target ILP variant: The overhead table references num_vars and num_constraints, which correctly match the ILP size fields. However, the issue does not specify which ILP variant (bool or i32) is the target. Since the formulation mixes binary (x_{i,p}) and integer (B) variables, it should target ILP<i32> with explicit bounds on B and x variables, or address how to handle the mixed variable types.

3. Missing GraphBandwidth model: The issue depends on a source problem that does not exist in the codebase and has no corresponding [Model] issue. A [Model] GraphBandwidth issue should be filed first.

Recommendations

• File a [Model] GraphBandwidth issue before or alongside this rule issue, defining the problem's fields (graph, num_vertices, num_edges, bandwidth objective) and getter methods
• Clarify the target ILP variant — the mixed binary/integer formulation suggests ILP<i32> with explicit upper and lower bounds on all variables
• Note that Caprara & Salazar-Gonzalez (2005) also propose tighter LP relaxations and branch-and-bound strategies that go beyond this basic formulation — consider citing these as context even if the reduction only uses the basic assignment formulation

[GiggleLiu]

On Hold

This rule depends on a source model that is not implemented on main.
I do not see a PR that added the model.
Issue #133 was closed as a duplicate, so the canonical source name is still unresolved here (GraphBandwidth vs Bandwidth).
Once the source model exists on main and the name is settled, this rule can resume.
If resumed, the target should be clarified as ILP<i32> with explicit x_{i,p} <= 1 bounds and B <= n - 1.

[GiggleLiu]

Fix-issue changelog

• Renamed source from GraphBandwidth to MinimumGraphBandwidth — matches model issue [Model] MinimumGraphBandwidth #133
• Specified target as ILP<i32> with explicit variable bounds: x_{i,p} ∈ [0,1], B ∈ [0, n−1]
• Updated overhead table to use getter method names: num_vertices^2 + 1, 2 * num_vertices + 2 * num_edges
• Replaced C₅ example with P₂×P₃ grid (6 vertices, 7 edges) — matches model issue [Model] MinimumGraphBandwidth #133 example, richer structure for round-trip testing
• Added suboptimal labeling comparison (row-major → B=3 vs column-major → B=2)
• Added explicit solution extraction step to the algorithm
• Resolves "On Hold" status: model [Model] MinimumGraphBandwidth #133 is now Ready with the name MinimumGraphBandwidth

Applied by /fix-issue.