3
$\begingroup$

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

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ thanks. What solver did you use ? do you think the result is sensitive to the solver? $\endgroup$
    – abcd
    Nov 27, 2023 at 10:19
  • $\begingroup$ @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. $\endgroup$
    – A.Omidi
    Nov 27, 2023 at 15:54

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.