Page 58 - IJOCTA-15-2

Multiple item economic lot sizing problem with inventory dependent demand

4.1.3. Obtaining the Initial Hybrid Solution a solution as an initial solution, we mean that we
use the setup vector of that solution as an initial
Clearly, it is best to run the sub-gradient algo- setup vector to fix in the MIP formulation for the
rithm as many iterations as possible to obtain multiple item ELSIDD problem. Similarly, when
the tightest bound (i.e. the lowest possible ob- we say we evaluate a solution, we mean that we
jective function value of the LR). Note that at solve the MIP formulation for a multiple item EL-
each iteration of the sub-gradient method, LR is SIDD problem with the values in the correspond-
solved for a different vector Λ. It is possible that ing setup vector fixed. In the following section,
in none of the iterations, solution to LR gives a we describe the details of the TSA, which we also
feasible to the original problem. However, it is summarize in Algorithm 3. Algorithm 4 summa-
also possible that in many of iterations, for some rizes the overall procedure.
Λ vectors, solutions to LR will be feasible to the
original problem (i.e., multiple item ELSIDD).
First, we come across feasible solutions during the 4.2. Details of the implementation of the
sub-gradient method. Then we take the y vector TSA
(i.e., setup vectors) of the best feasible solution
4.2.1. Solution representation
obtained, in addition to the y vector of the so-
lution obtained at the end of the 400 th iteration In metaheuristic algorithms, the solution repre-
of the sub-gradient method. Let’s refer to the sentation is a key component of the overall al-
first vector as y Lag,Best , and the latter as y 400 . gorithm design. It not only determines how the
Taking these two vectors, we run (on commercial solution is represented, but also determines how
software) the formulation for the multiple item the algorithm will search for improved solutions.
ELSIDD problem where we fix the common y it A good solution representation should encode the
entries of y Lag,Best and y 400 . In other words, we problem being solved effectively and should allow
run the formulation for the multiple item ELSIDD the algorithm to search for and evaluate poten-
where y it values are fixed to the corresponding val- tial solutions efficiently. In our TSA, we repre-
ues in the vector y 400 (or y Lag,Best ) only if those sent the solution by the binary setup vector y.
values are the same in both y Lag,Best and y 400 . This vector holds binary setup variables y it for
For instance, assume y Lag,Best = (1, 0, 0, 1, 1) and i = 1, . . . , N, t = 1, . . . , T. So, it is a vector
y 400 = (1, 1, 0, 1, 0), then common entries in both of dimension N × T. We determine the value of
st
vectors are the 1 , 3 rd and the 4 th entries. We such a solution by solving the MIP formulation of
st
fix the y it variables in the 1 , 3 rd and the 4 th the corresponding multiple item ELSIDD prob-
entries to 1, 0, and 1 respectively, and solve the lem where the binary setup variables are fixed to
MIP formulation of the multiple item ELSIDD the values in the binary setup vector y that rep-
(i.e., formulation (1)–(9)) to determine the rest of resents that particular solution. Recall that the
the variables, i.e., variables in the 2 nd and 5 th en- initial solution is obtained at the end of the sub-
tries. The setup vector y 400 might not be feasible, gradient optimization method in our TSA. As a
but (since y Lag,Best is feasible) their intersection matter of fact, we only use the setup vector y of
is guaranteed to be feasible. Now, suppose that that solution. We then reevaluate the objective
in none of the iterations, solution to LR gives a function value of that solution by solving the MIP
feasible solution to the original problem. In that formulation of the multiple item ELSIDD where
case, to hybridize with y 400 , we pick a y vector we fix y it values to the ones in y.
of a solution to LR obtained early in the sub- We want to remark that the mathematical
gradient method, i.e. at the 100 th iteration, which model of the multiple item ELSIDD problem has
is much before the method converges. We note two sets of binary decision variables: y it , i =
that even if no feasible solution is obtained in the 1, . . . , N, t = 1, . . . , T; and v , i = 1, . . . , N,
j
sub-gradient method, the solution to LR obtained t = 1, . . . , T, j = 1, . . . , J max it . Due to these
it
at the end of the sub-gradient method has a high binary variables, it is not easy for commercial
chance of being close to the feasible region since
solvers to find a solution to the multiple item EL-
Lagrange multipliers behave like penalty costs on
SIDD problem in a reasonable time. However,
the amount of production that exceeds capacity.
when y it variables are fixed, commercial solvers
We then use the resulting solution as an ini- can solve multiple-item ELSIDD problems in sec-
tial solution in our TSA. As described in Section onds due to the decreasing number of binary vari-
4.2, we define neighborhood with regard to the ables in the problem. Therefore, given its repre-
setup vector. In other words, our TSA searches senting y vector, the evaluation of a solution is
for the best setup vector. So, when we say we use relatively fast.
253