We survey the main results presented in the author's PhD Thesis presented in June 2003 at the Universite catholique de Louvain and supervised by Y. Pochet and L. A. Wolsey. The dissertation is written in English and is available from the author. In the first part of the thesis, we investigate the complexity and the polyhedral structure of various extensions of the uncapacitated single-item lot-sizing problem (Barany et al. 1984). In particular, we study models involving fixed charges on stocks, constant capacity and backlogging, and lower bounds on production. We describe algorithms, extended formulations, (facet-defining) valid inequalities and separation algorithms. Emphasis is placed on compact (i.e. of polynomial size) exact extended formulations. In a second part, we show how such extended reformulations for single-item problems can help to improve the solution of much more general production planning problems.
展开▼
机译：我们调查了2003年6月在卢瓦尔大学天主教大学发表并由Y. Pochet和L. A. Wolsey指导的作者博士学位论文中提出的主要结果。论文用英语撰写，作者可以索取。在本文的第一部分，我们研究了无能力的单项批量问题的各种扩展的复杂性和多面体结构（Barany等，1984）。尤其是，我们研究的模型涉及库存固定费用，恒定容量和积压以及生产下限。我们描述算法，扩展公式，（方面定义）有效不等式和分离算法。重点放在紧凑的（即多项式大小）精确扩展的公式上。在第二部分中，我们将说明对单项问题的这种扩展的重新表述如何帮助改善更一般的生产计划问题的解决方案。
展开▼
