期刊
MATHEMATICAL PROGRAMMING
卷 164, 期 1-2, 页码 129-155出版社
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-016-1079-2
关键词
Production sequencing; Unit commitment; Bounded up/down times; Interval-dependent startups; Tight MIP formulations; Convex hulls
类别
资金
- Interuniversity Attraction Poles Programme
- Belgian Science Policy Office
Switching machines on and off is an important aspect of unit commitment problems and production planning problems, among others. Here we study tight mixed integer programming formulations for two aspects of such problems: bounded length on- and off-intervals, and interval-dependent start-ups. The problem with both these aspects admits a general Dynamic Programming (shortest path) formulation which leads to a tight extended formulation with a number of binary variables that is quadratic in the number n of time periods. We are thus interested in tight formulations with a linear number of binary variables. For the bounded interval problem we present a tight network dual formulation based on new integer cumulative variables that allows us to simultaneously treat lower and upper bounds on the interval lengths and also to handle time-varying bounds. This in turn leads to more general results, including simpler proofs of known tight formulations for problems with just lower bounds. For the interval-dependent start-up problem we develop a path formulation that allows us to describe the convex hull of solutions in the space of machine state variables and interval-dependent start-up variables.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据