2025-11-16T08:07:11.605730

An $O(n\log n)$ Algorithm for Single-Item Capacitated Lot Sizing with a One-Breakpoint All-Units Discount and Non-Increasing Prices

Papadopoulos

This paper addresses the single-item capacitated lot sizing problem with a 1-breakpoint all-units quantity discount in a monotonic setting where the purchase prices are non-increasing over the planning horizon. For this case, we establish several novel properties of the optimal solution and develop a hybrid dynamic programming approach that maintains a compact representation of the solution space by storing only essential information about the states and using linear equations for intermediate values. Our algorithm runs in $O(n\log n)$ time, where $n$ denotes the number of periods. Our result is an improvement over the previous state-of-the-art algorithm, which has an $O(n^2)$ time complexity.

academic

単一品目容量制約ロットサイジング問題における $O(n\log n)$ アルゴリズム：単一ブレークポイント全量割引と非増加価格

基本情報

論文ID: 2510.11368
タイトル: An $O(n\log n)$ Algorithm for Single-Item Capacitated Lot Sizing with a One-Breakpoint All-Units Discount and Non-Increasing Prices
著者: Kleitos Papadopoulos
分類: cs.DS（データ構造とアルゴリズム）
発表時期: 2025年10月（arXiv プレプリント）
論文リンク: https://arxiv.org/abs/2510.11368

要旨

本論文は、単調非増加価格環境下における単一ブレークポイント全量割引を伴う単一品目容量制約ロットサイジング問題を研究している。著者は最適解の新たな性質を確立し、状態の重要情報のみを保存し線形方程式を用いて中間値を計算することで解空間の緊密な表現を維持するハイブリッド動的計画法を開発した。本アルゴリズムの時間計算量は $O(n\log n)$ であり、ここで $n$ は時間段数を表し、従来の最適アルゴリズムの $O(n^2)$ と比較して大幅な改善を実現している。

研究背景と動機

問題の重要性

ロットサイジング問題は製造業とサプライチェーン管理において中核的な位置を占めており、企業は需要を満たしながら調達費用と保管費用を含む総費用を最小化する必要がある。本問題の変種は実務に広く存在し、特に数量割引が存在する場合に顕著である。

既存手法の限界

論文で提供される関連研究との比較表から、既存アルゴリズムの時間計算量は以下の通り高い：

Federgruen and Lee (1990): $O(n^3)$
Atamtürk and Hochbaum (2001): $O(n^3)$ から $O(n^5)$
Malekian et al. (2021): $O(n^4)$
Down et al. (2021): $O(n^2)$ （現在の最適）

研究動機

著者は「ガソリンスタンド類比」を導入して問題を直感的に説明している：時間段はガソリンスタンドに対応し、在庫はタンク内の燃料に対応し、需要は駅間距離に対応し、品目費用は燃料価格に対応する。この類比はアルゴリズム設計の直感を理解するのに役立つ。

核心的貢献

最適解の構造的性質の確立：非減少価格と単一ブレークポイント割引条件下で、最適解が特定の数学的性質を有することを証明
ハイブリッド動的計画法アルゴリズムの提案：セグメント表現に基づく緊密な解空間表現方法を開発
$O(n\log n)$ 時間計算量の実現：既存の最適アルゴリズム $O(n^2)$ と比較して大幅な改善
効率的なデータ構造の設計：セグメント情報とMV閾値を維持するための拡張平衡二分探索木を使用

方法の詳細

問題定義

入力：

$n$ 個の時間段、各時間段 $t$ の需要 $d_t$
保管容量 $B(t)$ と単位保管費用 $h_t$
階層的価格関数： $p_t(x) = \begin{cases} p_{1,t}x & \text{if } x < Q \\ p_{2,t}x & \text{if } x \geq Q \end{cases}$
非増加価格： $p_{1,t} \geq p_{1,t+1}$ 、 $p_{2,t} \geq p_{2,t+1}$

出力：総費用を最小化する調達と保管戦略

目的関数： $\min_{x,I} \sum_{t=1}^n (p_t(x_t) + h_t I_t)$

制約条件：

$I_t = I_{t-1} + x_t - d_t$
$0 \leq I_t \leq B(t)$
$I_0 = 0$

コアアルゴリズムアーキテクチャ

1. 状態セグメント表現

著者は「状態セグメント」の概念を導入し、各セグメントは以下を含む：

明示的状態： $(f, dp(i,f))$ 、ここで $f$ は在庫水準、 $dp(i,f)$ はその状態に到達する最小費用
線形方程式：セグメント範囲内の暗黙的状態を生成するため
補助情報： $p(i,f)$ （最後に $p_2$ 燃料を取得した価格）、 $r(i,f)$ （利用可能な追加燃料量）

2. 重要補題

補題1（2Q界限）：任意の駅 $i$ において、最初の $2Q$ 個の状態を含む最適解集合 $S_b(i)$ は、最適解集合 $S_b(i+1)$ を構築するために必要なすべての状態を含む。

補題2（価格単調性）： $S_b(i)$ 内の任意の2つの状態 $dp(i,f)$ と $dp(i,w)$ で $f < w$ の場合、 $p(i,f) \geq p(i,w)$ が成立する。

補題3（連続性）：状態 $dp(i,f)$ が $S(i)$ 内の最適状態を生成するために使用される場合、生成された状態は連続区間を形成する。

3. MV閾値メカニズム

セグメント間の支配関係を効率的に処理するため、著者はMV（最大値）閾値を設計した：

通常MV（境界チェックポイント）： $MV(S_1) = \frac{dp(i,g) - dp(i,f)}{g-f}$

終点MV（ $S_2$ が右側で $p_{2,i}$ を使用する場合）： $MV_{term}(S_1) = \frac{dp(i,g) + T p_{2,i} - dp(i,f) - a p(i,f)}{L-a}$

アルゴリズムフロー

各駅の処理には以下が含まれる：

$p_{1,i}$ による剪定：支配されたセグメントを隣接から削除
$dp(i+1,0)$ の形成：直接到達と補充到達の費用を比較
$d(i,i+1)$ での分割：セグメントを到達可能と到達不可能に分類
一括更新：到達不可能なセグメントに $Q$ 単位の $p_{2,i}$ 燃料を追加
線形マージ： $[Q,2Q]$ 区間で一括更新セグメントと既存セグメントをマージ
最終剪定： $p_{1,i}$ による最後の支配性チェック

技術的革新点

1. セグメント表現の緊密性

従来の動的計画法は可能なすべての状態を明示的に保存する必要があるが、本論文のセグメント表現は重要な状態点と線形方程式のみを保存し、空間計算量を大幅に削減する。

2. MV閾値の効率性

MV閾値を事前計算し平衡二分探索木に維持することで、アルゴリズムは $O(\log n)$ 時間内にセグメント間の支配関係を判定できる。

3. 遅延更新メカニズム

一括更新と保管費用更新は遅延ラベルを採用し、不要な計算を回避し、アルゴリズムの効率性を維持する。

実験設定

理論分析

論文は主に理論分析を提供し、実験検証ではなく、以下を証明することに重点を置いている：

正確性：帰納法により、アルゴリズムが各駅で正確な $2Q$ -近似解集合を生成することを証明
時間計算量：
- 各駅で最大2つの新しいセグメントを作成
- 総セグメント数 $m_i \leq 2i$
- 各操作の時間計算量は $O(\log n)$
- 総時間計算量は $O(n \log n)$