3
$\begingroup$

If we consider the dynamic lot sizing problem with:

  • $d_i$ as the demand per period $i$ and denote $\sum_{i=1}^t d_i$ being the total demand up to period $t$, where $t$ can take values $1, \dots, T$ in a $T$-period problem.

  • $z_i$ is the amount ordered in period $i$ and denote $\sum_{i=1}^t z_i$ being the total amount ordered up to period $t$, where also $t$ can take values $1, \dots, T$ in a $T$-period problem.

  • $\delta_t$ is a boolean variable that indicates whether or not an order is placed in period $t$.

And then consider to have two constraints, which can be read as:

  1. The total supply must be at least as large as the total demand through the end of each period.

  2. The amount purchased in a period cannot exceed the total demand in that and future periods in the planning horizon.

One way to write out these constraints is:

(1.1)$$\sum_{i=1}^t z_i \ge \sum_{i=1}^t d_i,$$ where $t=1, \dots , T, $

(1.2)$$ z_t \le \delta_t \sum_{i=t}^T d_i,$$

where $t= 1, \dots, T$.

But for example in the paper of Wagelmans, Hoesel and Kolen where they present their eponymous algorithm, they introduce the variable $z_{ti}$, which is said to be the amount of period $i$'s demand that is produced in period $t$ and $\sum_{i=t}^T z_{ti} = z_t$

And then they rewrite the former two constraints as:

(2.1) $$\sum_{t=1}^i z_{ti} = d_i$$ where $i=1, \dots, T,$

(2.2) $$d_i\delta_t \ge z_{ti},$$ where $i=t, \dots, T$ and $t=1,\dots,T.$

But (1.2) and (2.2) seem to be NOT the same. Can anyone explain why the constraint equations (1.1) and (1.2) are identical to (2.1) and (2.2) ?

For those interested in the paper of WHK: https://www.researchgate.net/publication/46431739_Economic_Lot_Sizing_An_On_log_n_Algorithm_That_Runs_in_Linear_Time_in_the_Wagner-Whitin_Case

I use the notations of: http://eprints.stiperdharmawacana.ac.id/16/1/%5BJohn_A._Muckstadt,_Amar_Sapra%5D_Principles_of_Inve(BookFi).pdf

$\endgroup$
7
  • $\begingroup$ Would you say please, why you are trying to predefine lot size in the tables $1$ and $2$? AFAIK, the lot size values are decision variables. are those values calculated based on the specific method in the paper or the mentioned examples? $\endgroup$
    – A.Omidi
    Jan 17 at 13:20
  • $\begingroup$ The lot sizes are the decision variables, but I'm concerned about the constraints. The constraints define the set of admissible lot sizes per period., so I used two examples with predefined (not calculated and thus not optimal) lot sizes just to be able to evaluate the constraints. $\endgroup$ Jan 17 at 13:33
  • $\begingroup$ Thanks for your clarifying. I think this is the point you are confusing that. lot size values should be calculated through the optimization model w.r.t the defined constraints. It makes sense the solution satisfies all of the constraints. Do you try invoking the solution by solving the MP model and comparing this with your pre-defining values? $\endgroup$
    – A.Omidi
    Jan 17 at 13:34
  • $\begingroup$ But the point is that the second constraint seems useless to me or not working correctly. The constraints define my search space, so if producing 40 items in the first period doesn't violate the constraints, I won't be able to meet the constraint of "The amount purchased in a period cannot exceed the total demand in that and future periods in the planning horizon" and then I can use any optimization model, but it just won't work. The confusion with me is solely on the $z_{ti}$ definition which I seem to be misinterpreting and is poorly defined in the paper. $\endgroup$ Jan 17 at 13:50
  • $\begingroup$ Please, let me come back to my last question. "Do you try invoking the solution by solving the MP model and comparing this with your pre-defining values?". How do you ensure that the solution you mentioned in the examples would be an optimal or at least a feasible solution? $\endgroup$
    – A.Omidi
    Jan 17 at 13:55

1 Answer 1

5
$\begingroup$

The two sets of constraints are not the same, but both sets provide a formulation for the problem. The relationship between the two is that if you take a solution to (2.1) and (2.2), compute $z_t=\sum_i z_{ti}$, and substitute those values for $z_t$ everywhere in (1.1) and (1.2), keeping $\delta_t$ from the solution to (2.1) and (2.2), the constraints (1.1) and (1.2) will be satisfied. Actually doing this is a useful exercise for understanding.

This correspondence works in only one direction, though. The second formulation is tighter in the sense that there are (fractional) solutions to (1.1) and (1.2) that cannot be disaggregated into a solution of (2.1) and (2.2). Finding such a solution is another useful exercise.

$\endgroup$
2
  • $\begingroup$ Thanks! Just one small question: with "(fractional) solutions to (1.1) and (1.2)", do you mean that $0 \le \delta_t \le 1$ ? So that when for example you have a demand horizon of 3 periods with demand set {10, 15, 5}, you can choose $\delta_1$ to be e.g. $0.8$ and let $z_1$ be $24$, but aggregating this to $z_{ti}$'s will have $z_{11}$ to be $10$ and $\delta_1d_1 = 8$ and fail to (2.1) and (2.2). $\endgroup$ Jan 19 at 17:17
  • 1
    $\begingroup$ Yes, that's the idea, except that splitting $z_t$ to multiple $z_{ti}$ variables is disaggregation. $\endgroup$
    – RobPratt
    Jan 19 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.