Linearization of two constraints: one with a conditional max and one with a sum with a variable as index

Question

I have these two quite nasty constraints I have tried to linearize. I am trying to dynamically control if you are allowed to plan producing product p. You are allowed to do it if the product arrived (if $y_{t,p}\geq 0$ at time t, p has arrived at time t) before your last QC. In the constraints below $QC_t$ is a binary variable, $\text{last}\_{QC}_t$ would be an integer variable, $X_{t,p}^{\text{plan}}$ is a non-negative real variable and $y_{t,p}$ is a parameter.

\begin{align} \text{last}\_{QC}_t &= \max(\{k \leq t \mid QC_k = 1\}) \\ \sum_{k \leq \text{last}\_{QC}_t} y_{k,p} &\geq X_{t,p}^{\text{plan}} \end{align}

Linearization:

These should be the linearization of the conditional max constraint:

\begin{align} \sum_{k \leq t} \delta_{k,t} &= 1 &&\forall t \in T \\ \delta_{k,t} &\leq QC_k &&\forall t, k\leq t \in T \\ \delta_{k,t} &\leq \sum_{i=k}^t QC_i &&\forall t, k\leq t \in T \end{align}

This should be the linearization of the sum with a variable as index:

$$\sum_{k \leq t} \sum_{j \leq k} \delta_{k,t} \cdot y_{j,p} \geq X_{t,p}^{\text{plan}}$$

I hope my problem is clear and someone can answer if the linearization is okay.

Answer 1

Here's a straightforward derivation of a linearization that does not assume that $QC_t=1$ for some $t$. Use the Iverson bracket to rewrite $$\sum_{k \le \text{last}\_{QC}_t} y_{k,p} \ge X_{t,p}^{\text{plan}}$$ as $$\sum_{k \le t} [k \le \text{last}\_{QC}_t] y_{k,p} \ge X_{t,p}^{\text{plan}}$$ and introduce binary decision variable $z_{k,t}$ to replace the bracket: \begin{align} \sum_{k \le t} z_{k,t} y_{k,p} &\ge X_{t,p}^{\text{plan}} \tag1\label1\\ z_{k,t} &\iff k \le \text{last}\_{QC}_t \tag2\label2 \end{align} Because $y_{k,p} \ge 0$, we can replace \eqref{2} with $$z_{k,t} \implies k \le \text{last}\_{QC}_t \tag3\label3$$ Now to enforce \eqref{3}, we want $$z_{k,t} \implies \bigvee_{j=k}^t QC_j \tag4\label4$$ You can linearize \eqref{4} as $$z_{k,t} \le \sum_{j=k}^t QC_j \tag5\label5$$ So \eqref{1} and \eqref{5} yield one linearization.

You can optionally sparsify \eqref{5} by replacing it with \begin{align} z_{k,t} \le QC_k + z_{k+1,t} \tag6\label6 \end{align}