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

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

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

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.

• Your suggestion to impose $M \ge 0$ and $M \ge S - 35$ and then put $-M$ in the minimization objective does not work. There is nothing to prevent taking an arbitrarily large $M$. – Rob Pratt Oct 26 '19 at 0:38
• I dont understand the proposed solution. If S < 35, I dont want any effect on the Objective function. If I'd include (S−35)×M and −M to Objective function, then a value of (for instance) S=33 will add -3M to Objective function. But the goal was to have no Objective function effect if S<35. – Bjørn Sigurd Benestad Johansen Oct 26 '19 at 18:58
• @BjørnSigurdBenestadJohansen, I mentioned that in my answer but you are right, it needs more details. I am editing my answer. – Oguz Toragay Oct 26 '19 at 19:48
• @BjørnSigurdBenestadJohansen, please check the edited answer, I hope it will work this time. – Oguz Toragay Oct 26 '19 at 22:26
• Hi Oguz Toragay, Without having looked 100% through the details of your answer, it looks to me like you are on the right track. (Altough I would perhaps assume that 1 (not 2) binary variable would be enough). Anyway, for my problem, this gets a bit too complex and/or I get a bit worried about execution time, so I I think I will try to reformulate the original problem in order to avoid even more binary variables than those I already have... ;) Using CBC, I currently am at about 30-120 seconds solutions time, and I need to be careful not to increase solution time further... :) – Bjørn Sigurd Benestad Johansen Oct 27 '19 at 22:01