Why are these constraint equations equal?

Question

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

Answer 1

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.