Linear Programming: Objective function goodness if variable holds value above a given constant value

Question

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

• Variable $M$ is included in (minimize) objective function such that $M\ge0$ and $S-M-35\le0$.

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

Answer 1

For anyone reading the post. I have got the following answer:

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

Answer 2

You can easily add $(S-35)\times N$ to your objective function where $N$ is a big constant number. It works in two ways in a minimization problem:

• If $S \ge 35$ then you will have punishment in your objective function.
• If $S \le 35$ then it will decrease the objective function by the magnitude of $N$.

While in your approach: when you don't want the effect of $S\le 35$ in the objective function you can do the following:

Define $p$ and $q$ as binary variables and add all the following constraints to the model ($B$ is a big positive constant number): $$S\le 35 \times p + B\times q$$ $$S\ge 35 \times p - B\times p$$ $$p+q=1$$ $$M \ge -B\times q$$ $$M \le B\times q$$ $$M \le S-35+B\times p$$ $$M \ge S-35-B\times p$$ $p=1$ when $S\le35$ and $q=1$ when $S\ge35$. In each of these situation only two of the last four constraints will be active. When $p=1 \rightarrow M=0$ and when $q=1 \rightarrow M=S-35$. Now you can add $-M$ to your objective function.