The single-item lot-sizing polytope with continuous start-up costs and uniform production capacity

In this work we consider the uniform capacitated single-item single-machine lot-sizing problem with continuous start-up costs. A continuous start-up cost is generated in a period whenever there is a nonzero production in the period and the production capacity in the previous period is not saturated. This concept of start-up does not correspond to the standard (discrete) start-up considered in previous models, thus motivating a polyhedral study of this problem. In this work we explore a natural integer programming formulation for this problem. We consider the polytope obtained as convex hull of the feasible points in this problem. We state some general properties, study whether the model constraints define facets, and present an exponentially-sized family of valid inequalities for it. We analyze the structure of the extreme points of this convex hull, their adjacency and bounds for the polytope diameter. Finally, we study the particular case when the demands are high enough in order to require production in all the periods. We provide a complete description of the convex hull of feasible solutions in this case and show that all the inequalities in this description are separable in polynomial time, thus proving its polynomial time solvability.

We would like to thank the anonymous reviewers of a first version of this manuscript, whose comments helped us to improve the final version and presentation of the results. In particular, we are greatly indebted to one of them for pointing us to the elegant proof of Theorem 10. We are also greatly indebted to the anonymous reviewer of this submission for his/her thorough comments and suggestions, and very specially for the suggestions that led to the results in Sect. 4.1. This work was partially supported by Grants PIP-ANPCyT 0361 and PID-UNR 415 (Argentina).

Authors and Affiliations

1. CONICET, Buenos Aires, Argentina

   Mariana Escalante

2. Departamento de Matemática, FCEIA, Universidad Nacional de Rosario, Rosario, Argentina

   Mariana Escalante & María del Carmen Varaldo

3. Instituto de Ciencias, Universidad Nacional de General Sarmiento, Buenos Aires, Argentina

   Javier Marenco

Corresponding author

Correspondence to Mariana Escalante.

Appendix: An example

In this last section we summarize the results presented in Sect. 4 in a particular example. We consider the problem with a planning horizon consisting of periods T = \(\{1, \ldots , 5\}\). For periods in T, we have demands \(d = (0.8, 0.7, 0.8, 0.9, 0.9)\). It verifies the conditions \(d_i<1\) for \(1 \in T\) and \(k_{\mathrm{{\small prod}}}=5\). Using the PORTA package (see http://www.zib.de/Optimization/Software/Porta/) we obtain the following description of P by equations and linear inequalities.

The following remarks categorize these 25 facets within the model constraints and the known families of valid inequalities.

• The equalities (1a)–(6a) correspond to the minimal equation system for P.

• The constraint (1b) corresponds to the total demand satisfaction (see Theorem 3(i)).

• The inequalities (17b)–(21b) induce facets as we prove in Theorem 3(ii).

• The constraints (22b)–(25b) correspond to the inequalities inducing facets in Theorem 3(v).

• The constraints (12b), (14b), (15b) and (16b) belong to the family of \((k_0,M)\) -inequalities (see Remark 1) which define facets for P (see Theorem 4).

• The constraints (1b)–(11b) and (13b) are \((k_0,M)\)-inequalities (see Definition 1 and Theorem 5).

Reprints and permissions