# Will adding this constraint help my model?

I am solving a maximization problem with continuous variables $$x,z\in \mathbb{R}^+$$ and binary variable $$\delta \in \{0,1\}$$.

I am maximizing $$x$$ subject to side constraints and would like to enforce $$\delta = 1\implies x= z$$ and $$\delta = 0\implies x= 0$$ which I model as follows: \begin{align} x &\le z \tag{1}\\ 0 \le x &\le U \cdot \delta \tag{2} \end{align} where $$U$$ is an upper bound for variable $$x$$. Since I am maximizing $$x$$ this is sufficient. However, would it help the solver to add a lower bound to the above constraint $$(1)$$ ? Such as: $$z-U(1-\delta) \le x \le z \tag{3}$$

In other words, does model $$(2)-(3)$$ provide a tighter linear relaxation than model $$(1)-(2)$$?

#### Edit

• Note that it is important that the model remains linear. The above is a linearization of $$x=z \delta$$, which is not linear.
• Assume that $$U$$ is the best constant upper bound for variable $$x$$.

I think the answer is a definitive "maybe". Adding constraint (3) might help the solver to recognize infeasible branches of the search tree sooner (branches with $$\delta = 1$$ where side constraints would block $$x$$ from equaling $$z$$), which might help. On the other hand, it is also possible that the (3) would just be extra baggage that would slow the solver (slightly, if $$x$$ and $$z$$ have dimension 1). It is easy enough to try.

I tried to test a simple example of what you proposed. I am setting an upper and lower bound $$[0,5]$$, $$[0,4]$$ to the variables $$x$$ and $$z$$ respectively. By turning off the pre-solving, heuristics, and cuts the following results are shown:

1- the constraints $$(1)-(2)$$:

Presolving Time: 0.00

time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl.
0.0s|     1 |     0 |     3 |     - |   653k |   0 |   4 |   4 |   4 |   0 |  0 |   0 |   0 |-4.000000e+00 |      --      |    Inf | unknown
0.0s|     1 |     2 |     3 |     - |   655k |   0 |   4 |   4 |   4 |   0 |  1 |   0 |   0 |-4.000000e+00 |      --      |    Inf | unknown
* 0.0s|     2 |     0 |     4 |   1.0 |    LP  |   1 |   4 |   4 |   4 |   0 |  1 |   0 |   0 |-4.000000e+00 |-4.000000e+00 |   0.00%|  81.66%


2- the constraint $$(2)-(3)$$:

Presolving Time: 0.00

time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl.
* 0.0s|     1 |     0 |     1 |     - |    LP  |   0 |   4 |   1 |   1 |   0 |  0 |   0 |   0 |-4.000000e+00 |-4.000000e+00 |   0.00%| unknown
0.0s|     1 |     0 |     1 |     - |   651k |   0 |   4 |   1 |   1 |   0 |  0 |   0 |   0 |-4.000000e+00 |-4.000000e+00 |   0.00%| unknown


3- Also, it seems in the second case, only the third constraint is sufficient. (At least in my tiny example). By that, the results are the same as in case two:

Presolving Time: 0.00

time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl.
* 0.0s|     1 |     0 |     1 |     - |    LP  |   0 |   4 |   1 |   1 |   0 |  0 |   0 |   0 |-4.000000e+00 |-4.000000e+00 |   0.00%| unknown
0.0s|     1 |     0 |     1 |     - |   651k |   0 |   4 |   1 |   1 |   0 |  0 |   0 |   0 |-4.000000e+00 |-4.000000e+00 |   0.00%| unknown


it seems in cases $$(2)$$ and $$(3)$$ the solver needs a smaller number of branching to prove optimality.

• thanks. What solver did you use ? do you think the result is sensitive to the solver?
– abcd
Commented Nov 27, 2023 at 10:19
• @abcd, I used SCIP. As far as I know different solvers have different internal mechanism to encounter the problem, but by turning off thair arsenals like presolving and etc. the result may not make the difference. At least SCIP and CPLEX had the same behavior in this case. Commented Nov 27, 2023 at 15:54