2
$\begingroup$

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} $$

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

2 Answers 2

4
$\begingroup$

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

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

Obj: $min \ cx + dy + w\epsilon$
3 additional constraints
$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})]$

$\endgroup$
1
  • $\begingroup$ Are you assuming that $x$ and $y$ are integer variables? This was not stated in the original question. $\endgroup$
    – prubin
    Commented Nov 20, 2022 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.