9
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Rob Pratt Oct 26 '19 at 0:38
  • $\begingroup$ 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. $\endgroup$ – Bjørn Sigurd Benestad Johansen Oct 26 '19 at 18:58
  • $\begingroup$ @BjørnSigurdBenestadJohansen, I mentioned that in my answer but you are right, it needs more details. I am editing my answer. $\endgroup$ – Oguz Toragay Oct 26 '19 at 19:48
  • $\begingroup$ @BjørnSigurdBenestadJohansen, please check the edited answer, I hope it will work this time. $\endgroup$ – Oguz Toragay Oct 26 '19 at 22:26
  • 1
    $\begingroup$ 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... :) $\endgroup$ – Bjørn Sigurd Benestad Johansen Oct 27 '19 at 22:01

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.