Convert summation of min functions into linear constraints for optimization

Question

I have the following optimization problem: $$ \mbox{maximize } j^{*} \mbox{ subject to:} \sum_{j^{*}\leq j\leq J} \min({\bf A}_j,{\bf B}_j) \geq \lambda, \lambda \in \mathbb{R} \mbox{ and } {\bf A}_j,{\bf B}_j > 0 \forall j $$ where the values of $\bf A \in \mathbb{R}^n$ and $\bf B \in \mathbb{R}^n$ (constants) are dependent on their index $j$ in an arbitrary relationship (i.e. their values are arbitrarily predefined). $\lambda$ here is a constant and independent of $j$ or $j^*$. I am looking for an approach to convert this into a series of linear constraints if it is possible.

I have came across this question and this question which deals with the conversion of constraints containing minimum or maximum functions. However I am not sure if a similar method is possible when the summation function is wrapped over the minimum function, or whether the lack of knowledge on the nature of the entries of $\bf A$ and $\bf B$ mean that any attempt would not be possible.

(One point that might be worth nothing is that the constraint might be relaxed because it can be inferred that: $$ \min\left\{\sum_{j^{*}\leq j\leq J} {\bf A}_j, \sum_{j^{*}\leq j\leq J} {\bf B}_j\right\} \geq \sum_{j^{*}\leq j\leq J} \min({\bf A}_j,{\bf B}_j) $$ from which a conversion to linear constraints is indeed possible, from which feasible but suboptimal solutions can still be found. However in the context of my problem this constraint is best not to be relaxed.)

Answer 1

This becomes easier if you reformulate your expression as $$\sum_{0\leq j\leq J} \min({\bf A}_j,{\bf B}_j) \text{ if } j \geq j^{*} \text{ else } 0$$

Then you can linearize each operation separately using indicator constraints or the big-M methods described in the answers you linked. I.e. you can define a boolean variable equal to $j \geq j^{*}$ and a variable that will be equal to $\min({\bf A}_j,{\bf B}_j)$ as described in your links, and add similar big-M constraints for the if-else.

Note that some solvers and modelers can handle the above formula directly, with $\min$ and $\text{if}$/$\text{else}$, which will be much simpler than writing all big-M constraints yourself.