Optimization Online


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

Zeyang Zhang(zy_zhang***at***zju.edu.cn)
Chuanhou Gao(gaochou***at***zju.edu.cn)
James Luedtke(jim.luedtke***at***wisc.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 )


Download: [PDF]

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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society