discrete_optimization.lotsizing.uncapacitatedsingleitem.solvers package

Submodules

discrete_optimization.lotsizing.uncapacitatedsingleitem.solvers.cpsat module

CP-SAT solver for uncapacitated single-item lot sizing problem.

class discrete_optimization.lotsizing.uncapacitatedsingleitem.solvers.cpsat.CpSatUncapacitatedSingleItemSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: OrtoolsCpSatSolver

CP-SAT solver for uncapacitated single-item lot sizing.

This solver models the problem using: - Binary setup variables Y_t ∈ {0,1} for each period - Integer production variables X_t >= 0 for each period - Integer inventory variables I_t >= 0 for each period

Constraints: - Inventory balance: I_t = I_{t-1} + X_t - d_t - Setup forcing: X_t > 0 implies Y_t = 1 - Initial inventory: I_0 = 0

Objective: - Minimize: sum_t (s_t * Y_t + v_t * X_t + c_t * I_t)

The problem is uncapacitated, so there are no capacity constraints.

init_model(**kwargs: Any) → None

Initialize the CP-SAT model.

Parameters:

**kwargs – Additional parameters passed to parent class

problem: UncapacitatedSingleItemLSP

retrieve_solution(cpsolvercb: CpSolverSolutionCallback) → UncapacitatedSingleItemSolution

Extract solution from CP-SAT solver.

Parameters:

cpsolvercb – CP-SAT solver callback

Returns:

UncapacitatedSingleItemSolution

variables: dict

discrete_optimization.lotsizing.uncapacitatedsingleitem.solvers.dp module

class discrete_optimization.lotsizing.uncapacitatedsingleitem.solvers.dp.DpUncapacitatedLotSizingSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: DpSolver, WarmstartMixin

init_model(**kwargs: Any) → None

Initialize internal model used to solve.

Can initialize a ortools, milp, gurobi, … model.

problem: UncapacitatedSingleItemLSP

retrieve_solution(sol: Solution) → Solution

set_warm_start(solution: UncapacitatedSingleItemSolution) → None

Make the solver warm start from the given solution.

transition_name: dict

transition_objects: dict

discrete_optimization.lotsizing.uncapacitatedsingleitem.solvers.dp_wagner module

Wagner-Whitin dynamic programming solver for uncapacitated single-item lot sizing.

This module implements the classical Wagner-Whitin algorithm (1958) that solves the uncapacitated single-item lot sizing problem optimally in O(T²) time.

References

Wagner, H. M., & Whitin, T. M. (1958). Dynamic version of the economic lot size model. Management science, 5(1), 89-96.

class discrete_optimization.lotsizing.uncapacitatedsingleitem.solvers.dp_wagner.WagnerWhitinSolver(problem: UncapacitatedSingleItemLSP, **kwargs)

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

Solve the problem optimally using Wagner-Whitin algorithm.

Parameters:

**kwargs – Additional parameters (ignored)

Returns:

ResultStorage containing the optimal solution

discrete_optimization.lotsizing.uncapacitatedsingleitem.solvers.lp module

class discrete_optimization.lotsizing.uncapacitatedsingleitem.solvers.lp.GurobiUncapacitatedSingleItemSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: _BaseLpUncapacitatedSingleItemSolver, GurobiMilpSolver

convert_to_variable_values(solution: UncapacitatedSingleItemSolution) → dict[gurobipy.Var, float]

Convert a solution to a mapping between model variables and their values.

Will be used by set_warm_start().

Override it in subclasses to have a proper warm start. You can also override set_warm_start() if default behaviour is not sufficient.

class discrete_optimization.lotsizing.uncapacitatedsingleitem.solvers.lp.MathoptUncapacitatedSingleItemSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: _BaseLpUncapacitatedSingleItemSolver, OrtoolsMathOptMilpSolver

discrete_optimization.lotsizing.uncapacitatedsingleitem.solvers.toulbar module

class discrete_optimization.lotsizing.uncapacitatedsingleitem.solvers.toulbar.ToulbarUncapacitatedSingleItemSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: ToulbarSolver, WarmstartMixin

init_model(**kwargs) → None

Initialize internal model used to solve.

Can initialize a ortools, milp, gurobi, … model.

problem: UncapacitatedSingleItemLSP

retrieve_solution(solution_from_toulbar2: tuple[list, float, int]) → UncapacitatedSingleItemSolution

set_warm_start(solution: UncapacitatedSingleItemSolution) → None

Make the solver warm start from the given solution.

Module contents

Solvers for uncapacitated single-item lot sizing problem.

class discrete_optimization.lotsizing.uncapacitatedsingleitem.solvers.CpSatUncapacitatedSingleItemSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: OrtoolsCpSatSolver

CP-SAT solver for uncapacitated single-item lot sizing.

This solver models the problem using: - Binary setup variables Y_t ∈ {0,1} for each period - Integer production variables X_t >= 0 for each period - Integer inventory variables I_t >= 0 for each period

Constraints: - Inventory balance: I_t = I_{t-1} + X_t - d_t - Setup forcing: X_t > 0 implies Y_t = 1 - Initial inventory: I_0 = 0

Objective: - Minimize: sum_t (s_t * Y_t + v_t * X_t + c_t * I_t)

The problem is uncapacitated, so there are no capacity constraints.

init_model(**kwargs: Any) → None

Initialize the CP-SAT model.

Parameters:

**kwargs – Additional parameters passed to parent class

problem: UncapacitatedSingleItemLSP

retrieve_solution(cpsolvercb: CpSolverSolutionCallback) → UncapacitatedSingleItemSolution

Extract solution from CP-SAT solver.

Parameters:

cpsolvercb – CP-SAT solver callback

Returns:

UncapacitatedSingleItemSolution

variables: dict

class discrete_optimization.lotsizing.uncapacitatedsingleitem.solvers.WagnerWhitinSolver(problem: UncapacitatedSingleItemLSP, **kwargs)

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

Solve the problem optimally using Wagner-Whitin algorithm.

Parameters:

**kwargs – Additional parameters (ignored)

Returns:

ResultStorage containing the optimal solution