discrete_optimization.lotsizing.uncapacitatedsingleitem package

Subpackages

Submodules

discrete_optimization.lotsizing.uncapacitatedsingleitem.problem module

Single-item lot sizing problem implementations.

This module provides concrete implementations for single-item lot sizing variants: - UncapacitatedSingleItemLSP: Wagner-Whitin problem (ULSP) - CapacitatedSingleItemLSP: Single-item with capacity constraints

class discrete_optimization.lotsizing.uncapacitatedsingleitem.problem.Testttt[source]

Bases: WithoutCapacityProblem[int], WithoutBacklogProblem[int], WithoutChangeoverCostsProblem[int], WithoutSetupTimesProblem[int], WithoutParallelProductionProblem[int], WithoutStockLimitsProblem[int], GenericLotSizingProblem[int]

class discrete_optimization.lotsizing.uncapacitatedsingleitem.problem.UncapacitatedSingleItemLSP(demands: list[int] | ndarray, setup_costs: list[float] | ndarray, production_costs: list[float] | ndarray, inventory_costs: list[float] | ndarray)[source]

Bases: WithoutCapacityProblem[int], WithoutBacklogProblem[int], WithoutChangeoverCostsProblem[int], WithoutSetupTimesProblem[int], WithoutParallelProductionProblem[int], WithoutStockLimitsProblem[int], GenericLotSizingProblem[int]

Uncapacitated single-item lot sizing problem (ULSP / Wagner-Whitin problem).

This is the classical lot sizing problem: - Single product (item = 0) - No capacity constraints - No backlog allowed (demands must be satisfied on time) - No changeover costs (single item) - No setup times

Can be solved optimally in O(T²) with Wagner-Whitin dynamic programming.

The problem minimizes:

sum_t (s_t * Y_t + v_t * X_t + c_t * I_t)

Subject to:

I_t = I_{t-1} + X_t - d_t (inventory balance) X_t <= M * Y_t (big-M constraint for setup) X_t, I_t >= 0 (non-negativity) Y_t in {0, 1} (setup binary) I_0 = 0 (no initial inventory)

Where:

s_t: setup cost in period t v_t: production cost per unit in period t c_t: inventory cost per unit in period t d_t: demand in period t X_t: production quantity in period t Y_t: setup indicator (1 if production, 0 otherwise) I_t: inventory at end of period t

allows_lost_demand() → bool[source]
get_demand(item: int, period: int) → int[source]

Get demand for item in period.

get_inventory_cost_per_unit(item: int, period: int) → float[source]

Get inventory cost per unit.

get_production_cost_per_unit(item: int, period: int) → float[source]

Get production cost per unit.

get_setup_cost(item: int, period: int) → float[source]

Get setup cost.

get_solution_type()[source]

Return solution class for this problem.

property horizon: int

Number of time periods.

property items_list: list[int]

Single item with index 0.

class discrete_optimization.lotsizing.uncapacitatedsingleitem.problem.UncapacitatedSingleItemSolution(problem: UncapacitatedSingleItemLSP, production_periods: list[int] | None = None, production_quantities: list[int] | None = None)[source]

Bases: ProductionBasedSolution[int], WithoutBacklogSolution[int], WithoutCapacitySolution[int], WithoutChangeoverCostsSolution[int]

Solution for uncapacitated single-item lot sizing problem.

This uses ProductionBasedSolution which automatically computes: - Inventory levels - Delivery quantities - Backlog (0 for this problem)

From the production decisions.

problem: UncapacitatedSingleItemLSP
discrete_optimization.lotsizing.uncapacitatedsingleitem.problem.generate_random_instance(horizon: int, avg_demand: int = 10, setup_cost: float = 100.0, production_cost: float = 1.0, inventory_cost: float = 0.5, seed: int | None = None) → UncapacitatedSingleItemLSP[source]

Generate random instance for testing.

Parameters:

  • horizon – Number of periods

  • avg_demand – Average demand per period

  • setup_cost – Fixed setup cost per period

  • production_cost – Variable production cost per unit

  • inventory_cost – Inventory holding cost per unit

  • seed – Random seed for reproducibility

Returns:

Random problem instance

Module contents

Uncapacitated single-item lot sizing problem (ULSP / Wagner-Whitin problem).

This module provides the classical Wagner-Whitin problem and its optimal solver.

class discrete_optimization.lotsizing.uncapacitatedsingleitem.UncapacitatedSingleItemLSP(demands: list[int] | ndarray, setup_costs: list[float] | ndarray, production_costs: list[float] | ndarray, inventory_costs: list[float] | ndarray)[source]

Bases: WithoutCapacityProblem[int], WithoutBacklogProblem[int], WithoutChangeoverCostsProblem[int], WithoutSetupTimesProblem[int], WithoutParallelProductionProblem[int], WithoutStockLimitsProblem[int], GenericLotSizingProblem[int]

Uncapacitated single-item lot sizing problem (ULSP / Wagner-Whitin problem).

This is the classical lot sizing problem: - Single product (item = 0) - No capacity constraints - No backlog allowed (demands must be satisfied on time) - No changeover costs (single item) - No setup times

Can be solved optimally in O(T²) with Wagner-Whitin dynamic programming.

The problem minimizes:

sum_t (s_t * Y_t + v_t * X_t + c_t * I_t)

Subject to:

I_t = I_{t-1} + X_t - d_t (inventory balance) X_t <= M * Y_t (big-M constraint for setup) X_t, I_t >= 0 (non-negativity) Y_t in {0, 1} (setup binary) I_0 = 0 (no initial inventory)

Where:

s_t: setup cost in period t v_t: production cost per unit in period t c_t: inventory cost per unit in period t d_t: demand in period t X_t: production quantity in period t Y_t: setup indicator (1 if production, 0 otherwise) I_t: inventory at end of period t

allows_lost_demand() → bool[source]
get_demand(item: int, period: int) → int[source]

Get demand for item in period.

get_inventory_cost_per_unit(item: int, period: int) → float[source]

Get inventory cost per unit.

get_production_cost_per_unit(item: int, period: int) → float[source]

Get production cost per unit.

get_setup_cost(item: int, period: int) → float[source]

Get setup cost.

get_solution_type()[source]

Return solution class for this problem.

property horizon: int

Number of time periods.

property items_list: list[int]

Single item with index 0.

class discrete_optimization.lotsizing.uncapacitatedsingleitem.UncapacitatedSingleItemSolution(problem: UncapacitatedSingleItemLSP, production_periods: list[int] | None = None, production_quantities: list[int] | None = None)[source]

Bases: ProductionBasedSolution[int], WithoutBacklogSolution[int], WithoutCapacitySolution[int], WithoutChangeoverCostsSolution[int]

Solution for uncapacitated single-item lot sizing problem.

This uses ProductionBasedSolution which automatically computes: - Inventory levels - Delivery quantities - Backlog (0 for this problem)

From the production decisions.

problem: UncapacitatedSingleItemLSP
class discrete_optimization.lotsizing.uncapacitatedsingleitem.WagnerWhitinSolver(problem: UncapacitatedSingleItemLSP, **kwargs)[source]

Bases: SolverDO

Wagner-Whitin dynamic programming solver.

This solver computes the optimal solution for the uncapacitated single-item lot sizing problem in O(T²) time using dynamic programming.

The algorithm exploits the Zero Inventory Ordering (ZIO) property: In an optimal solution, production in period t (if any) should satisfy demand for an integer number of consecutive future periods, with zero inventory before period t.

This means we only need to consider T² possible solutions (for each period, consider producing to satisfy demand up to each future period).

The dynamic programming recurrence is:

f[t] = min over k in [0, t) of [f[k] + cost(k, t)]

Where:

f[t] = minimum cost to satisfy demands from period 0 to t-1 cost(k, t) = cost to produce in period k to satisfy demands k to t-1

= setup_cost[k] + production_cost[k] * sum(demands[k:t])

  • sum of inventory costs for holding from k to t

Base case: f[0] = 0 (no cost before first period)

Time complexity: O(T²) where T is the horizon Space complexity: O(T)

problem: UncapacitatedSingleItemLSP
solve(**kwargs) → ResultStorage[source]

Solve the problem optimally using Wagner-Whitin algorithm.

Parameters:

**kwargs – Additional parameters (ignored)

Returns:

ResultStorage containing the optimal solution

discrete_optimization.lotsizing.uncapacitatedsingleitem.generate_random_instance(horizon: int, avg_demand: int = 10, setup_cost: float = 100.0, production_cost: float = 1.0, inventory_cost: float = 0.5, seed: int | None = None) → UncapacitatedSingleItemLSP[source]

Generate random instance for testing.

Parameters:

  • horizon – Number of periods

  • avg_demand – Average demand per period

  • setup_cost – Fixed setup cost per period

  • production_cost – Variable production cost per unit

  • inventory_cost – Inventory holding cost per unit

  • seed – Random seed for reproducibility

Returns:

Random problem instance