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

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.

• Do you know that $QC_k=1$ for at least one $k$? In your proposed linearization, the second constraint dominates the third one. Commented Jul 13 at 3:52
• Yes $QC_k$ is equal to 1 for at least one k. Commented Jul 13 at 5:01
• y is not a variable but a parameter Commented Jul 13 at 5:43
• Is $\delta$ binary? What is its intended interpretation? Commented Jul 13 at 13:02

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}