5
$\begingroup$

Suppose I am minimizing a MILP and my objective is simply $\sum_i{x_i}$, where $x_i$ is binary. I also have a constraint saying that $1-\sum_j y_j = x_i$, $\forall i \in \mathcal{S}$, $\forall j \in \mathcal{S}$ where $\mathcal{S}$ is the set defining the indices of my variables and $y_i$ is binary. I have many other constraints on $y_i$, but none other on $x_i$. Basically, $x_i$ is going to be 1 (and contribute to the cost function) whenever $\sum_j y_j$ is not 1. Note that I have other constraints that force $\sum_j y_j \leq 1$.

Does it make sense to replace $1-\sum_j y_j = x_i$ by $1-\sum_j y_j \leq x_i$? Where by "make sense" I mean would the solver solve the problem more quickly by replacing the equality constraint by an inequality one?

Of course, with the inequality constraint, $x_i$ can be either 1 or 0 even when $\sum_j y_j$ is 1. However, since $x_i$ appears in the cost function and I'm minimizing, the solver would push $x_i$ to 0 if $\sum_j y_j =1$, so we would still get the desired value for $x_i$.

$\endgroup$

1 Answer 1

3
$\begingroup$

Would the solver solve the problem more quickly by replacing the equality constraint by an inequality one?

That depends. There are reasons why a solver could as the simplex might be smaller. There are reason why a solver might slow down. The "weaker" inequality constraint could break some presolving transformation.

Here are things i would look out for:

  • compare size of problem after presolving
  • time taken to solve
  • time per lp relaxtion
  • number of nodes explored till the solution is found

If the system after presolving is the same, it does not matter. A proxy for that is the size of the system. You ultimately care about the time it takes to solve. Differences in time per lp relaxtion and number of nodes explored till the solution is found can give you insight how the model will perform if you solve a larger problem.

$\endgroup$

Your Answer

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

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