# How can I include a penalty to my (linear) model?

Is it possible in a linear model to include a penalty if both variables $$x$$ and $$y$$ are greater than zero? I would like to have no penalty, if $$x$$ OR $$y$$ is zero.

For example, I have a model:

\begin{align} &\min_{x,y} c x + dy \\ \text{s.t.}& \\ & ax \le b \\ & zy \le e \\ & x,y \ge 0 \end{align}

• I suspect you want to enforce $$x\cdot y = 0$$ This is a complementarity constraint. No pure LP formulations for this. Commented Nov 18, 2022 at 16:36

You cannot do this within a linear program. If the penalty is a fixed amount (not proportional to the size of $$X$$ or $$Y$$), and assuming you can infer upper bounds $$M_X$$ and $$M_Y$$ on $$X$$ and $$Y,$$ you can do it by introducing binary variables $$W_X,$$ $$W_Y$$ and $$Z.$$ In the objective function, add the product of $$Z$$ and the penalty value you want. New constraints are $$X \le M_X \cdot W_X,$$ $$Y \le M_Y \cdot W_Y$$and$$Z\ge W_X + W_Y - 1.$$

• +1. You can optionally relax $Z$ to be nonnegative instead of binary. Commented Nov 18, 2022 at 16:28
• Indeed ... although I'm never sure whether a solver will be faster with or without the integrality restriction.
– prubin
Commented Nov 18, 2022 at 18:11
• And the solver might automatically detect and restore the integrality restriction that the user explicitly relaxed. :) Commented Nov 18, 2022 at 19:52
• Proving once again that the solver is smarter than I am. :-(
– prubin
Commented Nov 18, 2022 at 20:24

Obj: $$min \ cx + dy + w\epsilon$$
$$y >= w$$
$$x >= w$$
$$w >= {{x+y}\over M} - 1$$ where we is binary and M could be chosen such that $$1 < {{x+y}\over M} <= 2$$. My estimate M should be in this range $$[\lvert{b\over a}-{e\over z}\rvert,\max({b\over a}, {e\over z})]$$
• Are you assuming that $x$ and $y$ are integer variables? This was not stated in the original question.