[Model] ProductionPlanning

[isPANN]

Motivation

PRODUCTION PLANNING from Garey & Johnson, SS21. A classical NP-complete lot-sizing problem: given a multi-period planning horizon with per-period demands, production capacities, set-up costs, production costs, and inventory holding costs, can all demands be met within a total cost budget? Shown NP-complete by Florian, Lenstra, and Rinnooy Kan (1980) via reduction from PARTITION. The problem is solvable in pseudo-polynomial time but remains NP-complete even with equal demands, equal set-up costs, and zero inventory costs. A foundational hardness result for operations research, supply chain management, and manufacturing planning.

Associated rules:

• [Rule] Partition to Production Planning #488: Partition -> Production Planning (incoming, [Florian, Lenstra, and Rinnooy Kan, 1980])

Definition

Name: ProductionPlanning

Reference: Garey & Johnson, Computers and Intractability, SS21

Mathematical definition:

INSTANCE: Number n ∈ Z+ of periods, for each period i, 1 ≤ i ≤ n, a demand ri ∈ Z0+, a production capacity ci ∈ Z0+, a production set-up cost bi ∈ Z0+, an incremental production cost coefficient pi ∈ Z0+, and an inventory cost coefficient hi ∈ Z0+, and an overall bound B ∈ Z+.
QUESTION: Do there exist production amounts xi ∈ Z0+ and associated inventory levels Ii = ∑_{j=1}^{i}(xj−rj), 1 ≤ i ≤ n, such that all xi ≤ ci, all Ii ≥ 0, and
∑_{i=1}^{n}(pi·xi + hi·Ii) + ∑_{xi>0} bi ≤ B ?

Variables

• Count: n (one integer variable per period, representing production amount)
• Per-variable domain: {0, 1, ..., c_i} — production amount in period i, bounded by capacity
• Meaning: x_i is the production amount in period i. Inventory levels I_i are derived: I_i = sum_{j=1}^{i}(x_j - r_j). The constraints require all I_i >= 0 (no backlogging), all x_i <= c_i (capacity), and total cost (production + inventory + set-up) <= B.

Schema (data type)

Type name: ProductionPlanning
Variants: none (no type parameters; all values are non-negative integers)

Field	Type	Description
num_periods	usize	Number of planning periods n
demands	Vec<u64>	Demand r_i for each period i
capacities	Vec<u64>	Production capacity c_i for each period i
setup_costs	Vec<u64>	Set-up cost b_i for each period i (incurred if x_i > 0)
production_costs	Vec<u64>	Incremental production cost coefficient p_i per unit
inventory_costs	Vec<u64>	Inventory holding cost coefficient h_i per unit per period
cost_bound	u64	Overall cost bound B

Complexity

• Best known exact algorithm: The problem is NP-complete in general (Florian, Lenstra, and Rinnooy Kan, 1980), but solvable in pseudo-polynomial time via dynamic programming. When all capacities are equal, the problem can be solved in polynomial time (Florian and Klein, 1971). For the general capacitated lot-sizing problem with piecewise concave costs and a fixed number of breakpoints p, Koca, Yaman, and Akturk (2014) gave an O(n^(2p+3)) algorithm, later improved to O(n^(p+2) log n) by Ou (2017). In the worst case with arbitrary concave costs, no algorithm significantly improves upon pseudo-polynomial dynamic programming in O(n * B) or brute-force O*(product c_i) enumeration.
• Complexity string: (max_capacity + 1)^num_periods (brute-force enumeration over all production vectors)

Extra Remark

Full book text:

INSTANCE: Number n ∈ Z+ of periods, for each period i, 1 ≤ i ≤ n, a demand ri ∈ Z0+, a production capacity ci ∈ Z0+, a production set-up cost bi ∈ Z0+, an incremental production cost coefficient pi ∈ Z0+, and an inventory cost coefficient hi ∈ Z0+, and an overall bound B ∈ Z+.
QUESTION: Do there exist production amounts xi ∈ Z0+ and associated inventory levels Ii = ∑'_{j=1}(xj−rj), 1 ≤ i ≤ n, such that all xi ≤ ci, all Ii ≥ 0, and

∑_{i=1}^{n}(pi·xi + hi·Ii) + ∑_{xi>0} bi ≤ B ?

Reference: [Florian, Lenstra, and Rinnooy Kan, 1980]. Transformation from PARTITION.

Comment: Solvable in pseudo-polynomial time, but remains NP-complete even if all demands are equal, all set-up costs are equal, and all inventory costs are 0. If all capacities are equal, the problem can be solved in polynomial time [Florian and Klein, 1971]. The cited algorithms can be generalized to allow for arbitrary monotone non-decreasing concave cost functions, if these can be computed in polynomial time.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all production vectors (x_1,...,x_n) with 0 <= x_i <= c_i; compute inventory levels and total cost; check feasibility.)
• It can be solved by reducing to integer programming. (ILP: integer variables x_i, binary variables y_i (y_i=1 iff x_i>0), constraints I_i >= 0, x_i <= c_i, x_i <= c_i * y_i, and sum(p_ix_i + h_iI_i + b_i*y_i) <= B.)
• Other: Dynamic programming (pseudo-polynomial time) for fixed or bounded capacities.

Example Instance

Input:
n = 6 periods

Period i	Demand r_i	Capacity c_i	Setup cost b_i	Prod. cost p_i	Inv. cost h_i
1	5	12	10	1	1
2	3	12	10	1	1
3	7	12	10	1	1
4	2	12	10	1	1
5	8	12	10	1	1
6	5	12	10	1	1

Total demand = 5+3+7+2+8+5 = 30
Cost bound B = 80

Feasible production plan:
Produce in 3 batches: x = [8, 0, 10, 0, 12, 0].

Inventory levels (I_i = cumulative production − cumulative demand):

• I_1 = 8 − 5 = 3
• I_2 = 3 + 0 − 3 = 0
• I_3 = 0 + 10 − 7 = 3
• I_4 = 3 + 0 − 2 = 1
• I_5 = 1 + 12 − 8 = 5
• I_6 = 5 + 0 − 5 = 0

All x_i ≤ 12 ✓, all I_i ≥ 0 ✓

Cost breakdown:

• Production cost: ∑ p_i · x_i = 1·(8+10+12) = 30
• Inventory cost: ∑ h_i · I_i = 1·(3+0+3+1+5+0) = 12
• Setup cost: 3 setups × 10 = 30
• Total cost: 30 + 12 + 30 = 72 ≤ 80 ✓

Expected Outcome

Answer: YES — a feasible production plan exists with total cost 72 ≤ B = 80.

Brute-force validation (4,826,809 configurations): 52 feasible plans with 8 distinct cost values (72–80). The plan x = [8, 0, 10, 0, 12, 0] achieves the minimum cost of 72 among all feasible plans.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph
Non-trivial	✅ Pass	Distinct feasibility constraints and cost structure from all existing problems
Correctness	⚠️ Warn	Reference year mismatch; complexity section lacks a concrete worst-case bound
Well-written	❌ Fail	Example contains visible trial-and-error errors; no concrete complexity string for declare_variants!

Overall: 2 passed, 1 warning, 1 failed

---

Usefulness

ProductionPlanning does not exist in the codebase. No existing problem has the same combination of per-period demands, capacities, setup costs, production costs, and inventory holding costs. The issue identifies a planned incoming reduction from Partition (R150), which would connect it to the reduction graph.

Non-trivial

This is genuinely distinct from all existing models. The feasibility constraints (capacity bounds, non-negative inventory levels) combined with the mixed cost structure (linear production + linear holding + fixed setup costs) and the cost-budget decision question are unlike any current problem. It is not a variant of ILP, BinPacking, or any other existing model — it has its own unique input structure.

Correctness

References verified:

• Florian, Lenstra, and Rinnooy Kan: The issue cites this as "[1978]", but the paper "Deterministic Production Planning: Algorithms and Complexity" was published in Management Science 26(7):669–679 in 1980. A 1978 preprint existed (CWI preprint), but the standard citation year should be 1980. Minor inaccuracy.
• Florian and Klein (1971): Confirmed. "Deterministic Production Planning with Concave Costs and Capacity Constraints" established polynomial-time solvability for constant-capacity lot sizing. The O(T⁴) bound is well-documented.
• Koca, Yaman, and Aktürk (2014): Confirmed. Published in INFORMS Journal on Computing 26(4):767–779. The O(T^(2p+3)) bound for p breakpoints is correct.
• Ou (2017): The improvement to O(T^(p+2) log T) is referenced in the literature.
• Garey & Johnson A5 SS21: The Production Planning problem is indeed listed as SS21 (not A5 SS21 — "A5" appears to be a numbering artifact). This is a sequencing/scheduling category problem.

Complexity section weakness: The issue discusses several algorithmic results but never provides a concrete worst-case complexity string suitable for declare_variants!. For a satisfaction problem with pseudo-polynomial DP, the brute-force bound would be O*(∏cᵢ), but no specific expression is given. This is needed for implementation.

Well-written

Failures:

1. Example is broken and contains visible debugging. The example section shows the author's trial-and-error process: three failed attempts with inline "wait... infeasible" and "Too high" comments before finally changing B from 65 to 80. The final answer works (cost 79 ≤ 80), but the messy presentation is not suitable for the paper or implementation. The example should be a clean, single worked instance.

2. No concrete complexity string. The Complexity section discusses multiple algorithmic results qualitatively but does not provide a complexity expression in the format required by declare_variants! (e.g., "product_capacity_sum" or a concrete exponential bound). This is needed for implementation.

3. Inconsistent naming reference. The issue says "A5 SS21" but Garey & Johnson uses just "SS21" for sequencing/scheduling problems. The "A5" prefix is unclear.

Passes:

• All template sections are present and substantive
• The formal definition is mathematically well-formed and matches G&J
• Variables section correctly identifies the domain and semantics
• Schema is well-designed with appropriate field types
• Both brute-force and ILP solver paths are identified with good detail
• Symbol usage is mostly consistent between sections

Recommendations

• Clean up the example: pick one feasible plan, present it without the failed attempts
• Add a concrete complexity string for declare_variants! — suggest: the brute-force enumeration is O*(∏cᵢ), or if using pseudo-polynomial DP, O(n · C) where C = max capacity
• Fix the reference year: cite as Florian, Lenstra, and Rinnooy Kan (1980), not (1978)
• Consider a smaller example (e.g., 3–4 periods) that is easier to verify by hand

[isPANN]

Issue Quality Check — Model (Re-check)

Previous check: 2026-03-12. Re-check requested with --force. Issue body unchanged since previous check.

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; planned reduction from Partition
Non-trivial	✅ Pass	Distinct feasibility constraints and cost structure from all 112 existing problems
Correctness	⚠️ Warn	Reference year mismatch (1978 vs 1980); no concrete complexity string for declare_variants!
Well-written	❌ Fail	Example contains visible trial-and-error errors; no concrete complexity expression; simpler feasible plan exists

Overall: 2 passed, 1 warning, 1 failed

Previously: 2 passed, 1 warning, 1 failed → No change (issue body was not edited)

---

Usefulness

Pass. ProductionPlanning does not exist in the codebase (checked against all 112 registered problem types). The problem has a genuinely unique input structure: per-period demands, production capacities, setup costs, production cost coefficients, inventory holding cost coefficients, and a budget constraint. The issue identifies a planned incoming reduction from Partition (R150, Lenstra et al.), which connects it to the reduction graph.

Non-trivial

Pass. This is genuinely distinct from all existing models. The nearest neighbors are scheduling problems (MultiprocessorScheduling, FlowShopScheduling, PrecedenceConstrainedScheduling, etc.) and packing/knapsack problems — none of which combine per-period demand fulfillment, capacity constraints, non-negative inventory levels, and a mixed cost structure (linear production + linear holding + fixed setup) under a budget decision question.

Correctness

References verified:

• Florian, Lenstra, and Rinnooy Kan: The issue cites "[1978]", but the standard publication is Management Science 26(7):669–679, 1980. A 1978 CWI preprint existed, but the canonical citation year should be 1980. Minor inaccuracy (⚠️).
• Florian and Klein (1971): Confirmed. Polynomial-time solvability for constant-capacity lot sizing.
• Koca, Yaman, and Aktürk (2014): Confirmed. INFORMS Journal on Computing 26(4):767–779. O(T^(2p+3)) bound correct.
• Ou (2017): Improvement to O(T^(p+2) log T) referenced in the literature.
• Garey & Johnson SS21: Production Planning is SS21 in the Sequencing and Scheduling category. The "A5" prefix is non-standard — G&J uses just "SS21".

Complexity section weakness: The issue discusses multiple algorithmic results qualitatively but never provides a concrete worst-case complexity expression suitable for declare_variants!. For a satisfaction problem with brute-force enumeration over production amounts, a reasonable bound would involve the product of capacities or max_capacity^num_periods. No concrete expression is given. This is needed for implementation.

Well-written

Failures:

1. Example contains visible debugging/trial-and-error. The example section shows three failed attempts inline:

   • First attempt: I_6 = 4 - 5 = -1 ... wait, need x_5 = 13 but cap is 12.
   • Second attempt: revised plan, Total: 79 > B = 65. Too high.
   • Third attempt: another revision with I_3 = 4 - 7 = -3. Infeasible.
   • Finally changes B from 65 to 80 to make it work.

   This messy presentation is not suitable for the paper or implementation. The example should be a clean, single worked instance.

2. A simpler feasible plan exists. Python brute-force validation (4,826,809 configurations checked) found:

   • Claimed plan: x = [8, 0, 9, 0, 12, 1], cost = 79, 4 setups
   • Better plan: x = [8, 0, 10, 0, 12, 0], cost = 72, 3 setups (fewer setups AND lower cost)
   • The claimed solution is valid but suboptimal for illustrative purposes — the example should use the simpler plan instead.

3. No concrete complexity string. Missing a declare_variants!-compatible expression (e.g., "max_capacity^num_periods" or similar).

4. "A5 SS21" notation. G&J uses "SS21" — the "A5" prefix is unclear/non-standard.

Passes:

• All template sections present and substantive ✅
• Mathematical definition well-formed and matches G&J ✅
• Variables section correctly identifies domain and semantics ✅
• Schema well-designed with appropriate field types (Vec<u64>) ✅
• Both brute-force and ILP solver paths identified with detail ✅
• Symbol usage mostly consistent across sections ✅

Python validation stats:

• Total configurations: 4,826,809 (13^6)
• Feasible: 52 (0.001%)
• Infeasible: 4,826,757
• 8 distinct cost values among feasible plans (72–80)
• Minimum achievable cost: 72 (unique optimal plan)
• Instance is non-trivial ✅

Recommendations

• Clean up the example: use x = [8, 0, 10, 0, 12, 0] with cost 72 and B = 80 (or pick a tighter B like 75 for a more interesting near-threshold instance)
• Remove all failed attempts and present a single clean worked example
• Add a concrete complexity string: suggest "(max_capacity + 1)^num_periods" for brute-force enumeration
• Fix reference year: cite as Florian, Lenstra, and Rinnooy Kan (1980), not (1978)
• Change "A5 SS21" to just "SS21"
• Consider a smaller example (3–4 periods) that is easier to verify by hand while still having multiple feasible plans

[isPANN]

Fix-issue changelog

• Fixed author order: "Lenstra, Rinnooy Kan, and Florian" → "Florian, Lenstra, and Rinnooy Kan" (all occurrences)
• Fixed reference year: "(1978)" → "(1980)" — journal publication in Management Science 26(7):669–679
• Fixed G&J reference: "A5 SS21" → "SS21"; removed non-standard "(P205)" prefix
• Fixed associated rules: "R150:" → "[Rule] Partition to Production Planning #488:" (actual GitHub issue number)
• Added concrete complexity string: (max_capacity + 1)^num_periods (brute-force enumeration bound)
• Rewrote Example Instance: removed 3 failed attempts and trial-and-error debris; replaced with clean optimal plan x = [8, 0, 10, 0, 12, 0] (cost 72, 3 setups)
• Added Expected Outcome section with brute-force validation stats (52 feasible / 4,826,809 total, 8 distinct cost values)

All changes verified by Python brute-force validation.

Applied by /fix-issue.