[Model] ShortestWeightConstrainedPath

[isPANN]

---

name: Problem
about: Propose a new problem type
title: "[Model] ShortestWeightConstrainedPath"
labels: model
assignees: ''

Motivation

SHORTEST WEIGHT-CONSTRAINED PATH from Garey & Johnson, A2 ND30. A classical NP-complete problem that asks for a simple s-t path simultaneously satisfying both a length budget and a weight budget. This bicriteria path problem arises naturally in routing with quality-of-service constraints (e.g., minimize delay subject to a bandwidth constraint). NP-complete even on acyclic graphs, but solvable in polynomial time if all weights are equal or all lengths are equal.

Associated reduction rules:

• As source: None found in the current rule set.
• As target: R51: PARTITION -> SHORTEST WEIGHT-CONSTRAINED PATH

Note: The Partition problem does not yet exist in the codebase. It must be implemented before the associated reduction rule can be added.

Definition

Name: ShortestWeightConstrainedPath

Canonical name: SHORTEST WEIGHT-CONSTRAINED PATH (also: Weight-Constrained Shortest Path, Constrained Shortest Path, Resource-Constrained Shortest Path)
Reference: Garey & Johnson, Computers and Intractability, A2 ND30

Mathematical definition:

INSTANCE: Graph G = (V,E), length l(e) ∈ Z^+, and weight w(e) ∈ Z^+ for each e ∈ E, specified vertices s,t ∈ V, positive integers K,W.
QUESTION: Is there a simple path in G from s to t with total weight W or less and total length K or less?

Variables

• Count: |E| binary variables (one per edge), indicating whether the edge is included in the path.
• Per-variable domain: {0, 1} -- edge is excluded or included in the s-t path.
• dims(): vec![2; num_edges] — each edge has a binary choice (include or exclude).
• Meaning: The variable assignment encodes a subset of edges. A satisfying assignment is a subset S of E such that the subgraph induced by S forms a simple path from s to t, the sum of l(e) for e in S is at most K, and the sum of w(e) for e in S is at most W.

Schema (data type)

Type name: ShortestWeightConstrainedPath<G, N>
Variants: graph type (G), numeric type for lengths and weights (N)

Field	Type	Description
graph	G	The undirected graph G = (V, E)
lengths	Vec<N>	Edge length l(e) for each edge
weights	Vec<N>	Edge weight w(e) for each edge
source	usize	Index of source vertex s
target	usize	Index of target vertex t
length_bound	N	The length bound K
weight_bound	N	The weight bound W

Size fields (getter methods):

• num_vertices() -> usize — number of vertices in the graph
• num_edges() -> usize — number of edges in the graph

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• Has two simultaneous constraints (length and weight), which is what makes it NP-hard. With only one constraint it reduces to standard shortest path (polynomial).
• Generalizes to the Resource-Constrained Shortest Path Problem (RCSPP) with multiple resource constraints.
• The type parameter is named N (not W) to avoid collision with the weight bound symbol W in the mathematical definition.

Complexity

• Best known exact algorithm: Pseudo-polynomial time O(|V| · |E| · W_max) via dynamic programming over weight values (Lagrangian relaxation approaches). For the general case, exact algorithms are exponential. FPTAS exists with (1+ε) approximation on the weight constraint (Hassin, 1992; Lorenz and Raz, 2001).
• Classic algorithm: O(n · 2^n) via subset enumeration (Held-Karp style DP adapted for bicriteria).
• NP-completeness: NP-complete by transformation from PARTITION (Garey & Johnson, ND30). Also NP-complete for directed graphs.
• Special cases: Polynomial-time solvable if all weights are equal or all lengths are equal (reduces to single-criterion shortest path).

declare_variants! guidance:

crate::declare_variants! {
    ShortestWeightConstrainedPath<SimpleGraph, i32> => "2^num_edges",
}

The bound 2^num_edges reflects the brute-force search over all edge subsets. A tighter bound based on simple path enumeration is O(n · 2^n) where n = |V|, but since this problem has |E| binary variables, 2^num_edges is the natural choice matching the variable encoding.

• References:
  • R. Hassin (1992). "Approximation schemes for the restricted shortest path problem." Mathematics of Operations Research, 17(1):36-42.
  • D.H. Lorenz, D. Raz (2001). "A simple efficient approximation scheme for the restricted shortest path problem." Operations Research Letters, 28(5):213-219.
  • Garey & Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, Problem ND30.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), length l(e) ∈ Z^+, and weight w(e) ∈ Z^+ for each e ∈ E, specified vertices s,t ∈ V, positive integers K,W.
QUESTION: Is there a simple path in G from s to t with total weight W or less and total length K or less?
Reference: [Garey & Johnson, ND30]. Transformation from PARTITION.
Comment: Also NP-complete for directed graphs. Both problems are solvable in polynomial time if all weights are equal or all lengths are equal.

How to solve

• It can be solved by (existing) bruteforce -- enumerate all simple s-t paths and check both constraints.
• It can be solved by reducing to integer programming -- minimize total length subject to total weight <= W and path connectivity constraints.
• Other: Pseudo-polynomial DP in O(|V| * |E| * W_max); FPTAS with (1+epsilon) approximation.

Example Instance

Instance 1 (YES -- feasible path exists):
Graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 8 edges:

• s = 0, t = 5, K = 10, W = 8

• Edges (length, weight):

  • {0,1}: (2, 5)
  • {0,2}: (4, 1)
  • {1,3}: (3, 2)
  • {2,3}: (1, 3)
  • {2,4}: (5, 2)
  • {3,5}: (4, 3)
  • {4,5}: (2, 1)
  • {1,4}: (6, 1)

• Path 0 -> 2 -> 3 -> 5: length = 4+1+4 = 9, weight = 1+3+3 = 7. Both 9 <= 10 and 7 <= 8. YES.

• Path 0 -> 2 -> 4 -> 5: length = 4+5+2 = 11 > 10. Fails length bound.

• Path 0 -> 1 -> 3 -> 5: length = 2+3+4 = 9, weight = 5+2+3 = 10 > 8. Fails weight bound.

Instance 2 (NO -- no feasible path):
Same graph, K = 6, W = 4.

• Path 0->2->3->5: length=9 > 6. Fails.
• Path 0->1->3->5: length=9 > 6. Fails.
• Path 0->2->4->5: length=11 > 6. Fails.
• Path 0->1->4->5: length=2+6+2=10 > 6. Fails.
• No simple s-t path has both length <= 6 and weight <= 4.
• Answer: NO

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; connects via PARTITION reduction
Non-trivial	✅ Pass	Distinct bicriteria satisfaction problem unlike any existing model
Correctness	⚠️ Warn	Megiddo reference year may be incorrect (1979 found, not 1977); complexity section lacks a concrete worst-case bound for declare_variants!
Well-written	⚠️ Warn	Missing concrete complexity string; minor notation issues

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

The problem does not exist in the current codebase (24 problems checked). It is a classical NP-complete problem from Garey & Johnson (ND30) with a clear associated reduction (PARTITION → ShortestWeightConstrainedPath). The motivation is well-articulated: bicriteria path routing arises in QoS-constrained network design. The problem would add a new satisfaction problem to the graph category, which is currently dominated by optimization problems.

The "How to solve" section identifies brute-force, ILP, and DP approaches — all viable for verification. Pass.

Non-trivial

This is genuinely distinct from all existing problems in the codebase. No existing problem models a bicriteria path satisfaction problem. The closest existing problems are TravelingSalesman (single-objective tour, not path; optimization, not satisfaction) and ILP (general formulation). The dual-constraint structure (length AND weight budgets) on simple s-t paths is a fundamentally different feasibility condition. Pass.

Correctness

References verified:

• Garey & Johnson, ND30: The Shortest Weight-Constrained Path is a well-known problem in the GJ appendix (Network Design section). The problem statement in the issue matches the standard formulation. ✅
• Hassin (1992): "Approximation Schemes for the Restricted Shortest Path Problem," Mathematics of Operations Research 17(1):36-42. Confirmed — presents FPTAS for the constrained shortest path problem. ✅
• Lorenz & Raz (2001): "A simple efficient approximation scheme for the restricted shortest path problem," Operations Research Letters 28(5):213-219. Confirmed — improves Hassin's result. ✅
• Megiddo (1977): The issue cites "N. Megiddo (1977). On the complexity of some optimization problems." Web searches consistently find Megiddo's related work published in 1979 (Mathematics of Operations Research), not 1977. The 1977 date may refer to a technical report or preprint, but the exact title "On the complexity of some optimization problems" could not be independently verified. The NP-completeness of the constrained shortest path problem is well-established regardless. ⚠️ Warn — the year and exact title of the Megiddo reference could not be confirmed; may need correction.

Complexity section:

• The issue describes pseudo-polynomial DP in O(|V| * |E| * W_max) and a brute-force O(n * 2^n) bound, but does not provide a single concrete worst-case complexity string suitable for declare_variants!. The codebase requires a specific exponential bound like "2^num_vertices" — the issue should clarify which bound to use.
• The FPTAS references are correct but not directly relevant for exact solving complexity.

Well-written

4a — Information Completeness: All required sections are present and substantive: Motivation, Name, Reference, Definition, Variables, Schema, Complexity, How to solve, Example Instance. ✅

4b — Definition Completeness: The formal definition is well-formed with clear input, feasibility constraints (simple s-t path with total weight ≤ W and total length ≤ K), and decision criterion. This is a satisfaction problem (Metric = bool), correctly identified. ✅

4c — Symbol and Notation Consistency:

• The definition uses G = (V, E), l(e), w(e), s, t, K, W — all consistently used across sections. ✅
• The Schema section uses lengths and weights (plural Vec fields) which is clear. ✅
• Minor issue: The schema uses a single type parameter W for both lengths and weights. This reuses the symbol W which is also the weight bound in the definition. Consider using a different type parameter name (e.g., N for numeric type) to avoid confusion. ⚠️
• The issue does not specify getter method names for the overhead system (e.g., num_vertices(), num_edges()). These should be listed to enable declare_variants! complexity strings. ⚠️

4d — Example Quality:

• Instance 1 (YES): 6 vertices, 8 edges — non-trivial and brute-force verifiable. The worked example shows three candidate paths with arithmetic. ✅
• Instance 2 (NO): Same graph with tighter bounds, demonstrating infeasibility. ✅
• Both examples are detailed enough for paper use. ✅

Recommendations

• Verify or correct the Megiddo reference: the year may be 1979 (published in Mathematics of Operations Research) rather than 1977. Alternatively, provide a DOI or more precise citation.
• Add a concrete complexity string for declare_variants!, e.g., "2^num_vertices" based on the O(n * 2^n) Held-Karp-style DP mentioned in the issue.
• Consider renaming the type parameter from W to something like N to avoid collision with the weight bound symbol W in the mathematical definition.
• The category for this model file would be graph/ (since the input is a graph), making the file path src/models/graph/shortest_weight_constrained_path.rs.