In a linear programming formulation, stating that a punishment is to be introduced in an objective minimize function if a variable $S$ holds a value above a given constant $K$ (in the below example, $K = 35$), is quite easy:

  • Variable $M$ is included in the objective function to be minimized

  • $M \geq 0$

  • $S-M-35 \leq 0$

Exemplified explanation: If $S$ gets value $30$, then $M$ may be kept at $0$, so no punishment in objective function. However, if $S$ gets value $40$ in problem solution, $M$ is forced to at least $5$, and consequently a punishment of $5$ is included, just as desired.

But what if we want to include goodness in objective function if $S$ gets value above $35$? E.g., in the previous example, a value of $S$ equal to $30$ should (still) not influence the objective function. But a value of $S$ equal to $40$ should decrease the objective function cost with $5$.

I originally thought this "swap" from badness to goodness would be easy, but I worked on it for almost a full day without finding a solution.


In other words, you want to maximize $\max(S-35,0)$. You cannot maximize a max or minimize a min in linear programming because these problems are nonconvex. You would need to introduce binary variables.

In the badness example, you are instead minimizing $\max(S-35,0)$. Both minimizing a max and maximizing a min are doable with linear programming.

  • $\begingroup$ Thanks a lot! :-) I already had started to get the feeling that I need an auxiliary binary variable. FYI: In my case, I think I will end up with a problem redefinition and simply include a scaled down version of S (0.001 * S) directly in the objective function. Should be fair enough in my case. $\endgroup$ – Bjørn Sigurd Benestad Johansen Oct 25 '19 at 7:15

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.