New Valid Inequalities and Formulation for the Static Chance-constrained Lot-Sizing Problem

Zeyang Zhang(zy_zhangzju.edu.cn)
Chuanhou Gao(gaochouzju.edu.cn)
James Luedtke(jim.luedtkewisc.edu)

Abstract: We study the static chance-constrained lot sizing problem, in which production decisions over a planning horizon are made before knowing random future demands, and the backlog and inventory variables are then determined by the demand realizations. The chance constraint imposes a service level constraint requiring that the probability that any backlogging is required should be below a given threshold. We model uncertain outcomes with a finite set of scenarios, and begin by applying existing results about chance-constrained programming to obtain an initial extended mixed-integer programming formulation. We further strengthen this formulation with a new class of valid inequalities that generalizes the classical (l,S) inequalities for the deterministic uncapacitated lot sizing problem. In addition, we prove an optimality condition of the solutions under a modified Wagner-Whitin condition, and based on this derive a new extended mixed-integer programming formulation. We also discuss how our model and methods can be extended to a model in which the time horizon is split into two parts, where demands are known in the first part and random in the latter part. We conduct a thorough computational study demonstrating the effectiveness of the new valid inequalities and extended formulation.

Keywords: Lot sizing, chance constraints, valid inequalities

Category 1: Stochastic Programming

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Citation:

Download: [PDF]

Entry Submitted: 06/17/2021
Entry Accepted: 06/17/2021
Entry Last Modified: 06/17/2021

Modify/Update this entry