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.)

  • 1
    $\begingroup$ Are $A_j$ and $B_j$ decision variables or constants? $\endgroup$ – RobPratt Jun 9 '20 at 16:08
  • $\begingroup$ 1. If $\lambda$ is a constant, what does $\lambda \neq \lambda(j, j*)$ mean? (The right side appears to treat $\lambda$ as a function. $\endgroup$ – prubin Jun 9 '20 at 17:39
  • $\begingroup$ 2. Is the min function being used here to mean coordinate-wise minimization? $\endgroup$ – prubin Jun 9 '20 at 17:40
  • $\begingroup$ @RobPratt $A_j$ and $B_j$ are constants $\endgroup$ – jackson95 Jun 10 '20 at 1:40
  • 3
    $\begingroup$ Because everything is constant except $j^*$, you can just check the inequality for each $j^*$ from $J$ down to $1$, stopping as soon as it is satisfied. No solver required. $\endgroup$ – RobPratt Jun 10 '20 at 1:58

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.

  • $\begingroup$ Yes this should work. I think the tricky bit was how to remove $j^*$ from the lower bound of the summation index because it can't be guaranteed for solvers to handle that. After that either the big-M method or directly application of the expression should work. $\endgroup$ – jackson95 Jun 10 '20 at 14:36

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.