1. Introduction and Literature Review
Capacitated lot sizing problem (CLSP) is well studied in literature, see Verma  , and Verma and Sharma    for a summary of recent works on CLSP. For literature on reformulation of CLSP, see Pochet and Wolsey  and Miller and Nemhauser et al.  for a detailed exposition on reformulations of CLSP. In this paper we give a new approach which leads to a better reformulation of CLSP.
2. Formulation by Pochet and Wolsey 
t: Set of the Time period from 1, ・・・, n, for which we are taking decisions;
Definition of Constant
: Fixed setup cost in time period “t”;
: Per unit production cost in time period “t”;
: Demand in time period “t”, here demand is independent;
: Per unit inventory carrying cost in time period “t”;
: Per unit shortage cost in time period “t”;
: Production capacity in the time period “t”;
Definition of Variables
: Number of product produced in time period “t”;
: Binary variable takes value “1” if machine setup to produce in time period “t”, “0”, otherwise;
: In stock inventory at the end of time period “t”;
: Backlog in the end of period “t”;
Production balance constraints
Pochet and Wolsey  gave the following constraint that lead to reformulation:
SLCLSP as given by Pochet and Wolsey  is Model A1: Min (1); s.t. (2), (3), (4) and (6). By using (5) in place of (3) lead to reformulation (called Model A2: min (1); s.t. (2), (4), (5) and (6). Model A1 has less number of variables as variable “x” is eliminated.
We add a new constraint given below (see,  ) that can be used in place of (2):
Using (5) we get the following (called Model A3): Min Z1 (or (8)); s.t. (4), (5), (6), (7).
We use (7) to eliminate st from the problem A2 to get: Min Z2 (or (9)); s.t. (4), (5), (6).
It can be seen that model A3 has least number of variables; it is followed by A2 that has less number of variables compared to model A1 which is well known reformulation (Pochet and Wolsey  . We solve model A1, model A2, and
Table 1. Problem for 50 time period (Z value and No. of node processed in brand and bound procedure).
Table 2. Problem for 50 time period (Iteration and execution time in GAMS).
Table 3. Problem for 60 time period (Z value and No. of nodes).
Table 4. Problem for 60 time period (Iteration and execution time).
Table 5. Problem for 100 time period (Z value and No. of nodes).
Table 6. Problem for 100 time period (Iteration and execution time).
model A3 by using student version of GAMS available at IIT Kanpur; and find that our reformulations (model A3 and A2) have superior computational advantages than model has A1.
3. Preparing Test Problems and Results
We created problem instances with set up, inventory carrying, shortage and production cost are normally distributed with mean and variance given below:
Fixed cost: mean 100000 and variance 10000
Shortage cost: mean 5000 and variance 500
Inventory carrying cost: mean 600 and variance 60
Variable Production cost: mean1500 and variance 100
Demand and capacity were chosen from uniform distribution in the range of 10,000 - 15,000. In the case of infeasible solution, the capacity values are increased or demand values are decreased keeping other costs same. We created 50 problem instances each for periods 50, 60 and 100. Models A1, A2 and A3 were coded in GAMS and were solved in GAMS; and they were run in branch and bound mode. The GAMS solver returns a satisfactory solution obtainable in reasonable time. It is to be noted that these problems are NP-HARD and will take few billion centuries to come to optimal solution. Detailed data are given in appendix see Tables 1-6; and consolidated results of “t” test are given in Tables 7-9 below. Models A1, A2 and A3 are compared on the criteria of execution time,
Table 7. 50 Time period: t values.
Table 8. 60 Time period: t values.
Table 9. 100 time period: t values.
*Significant at 0.05 level; **significant at 0.01 level; ***significant at 0.001 level; In Table 7: 2.742**means that model A3 takes less time than model A1 and is significant at 0.01 level.
number of iterations and number of nodes evaluated in the search tree). On an average, A3 is superior to A1 and A2 and A2 is superior to A1 on most criteria; and large positive “t” values in the Tables 7-9 give adequate support in favor of A3.
4. Discussion and Conclusion
Thus it can be seen that model A3 has superior results in general (except for the case of execution time in 60 period problems) (here A3 is better than A1, but not statistically significant). This shows that the new formulation given by us is superior to models available in literature. This is the useful contribution we make. The three reformulations presented in this paper use Equation (5) and this leads
to To get , we need to develop good heuristics, and
show that the duality gap is as less as possible. We have already started work on this, and will come back with results as soon as possible.