5
$\begingroup$

Suppose that I have an MIP with a whole lot of continuous variables and some integer variables. In my case, this takes a very long to solve (in fact I wasn't able at all to solve it to optimality). So I was wondering if it would be beneficial for solving this problem to exchange my integer variables by multiple binary variables.

The integer variables do have upper bounds in the range of $10^2$, so I would replace them with ~100 binary variables. Does this help my LP relaxation to get stronger? Actually, I would suggest to slightly adjust objective function coefficients, so I don't end up with ~100 variables of the exact same nature (I guess this might help).

I would appreciate any experience or expertise on this topic, Cheers.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ This question is very relevant. $\endgroup$
    – rasul
    Commented Jul 13, 2021 at 11:13
  • 2
    $\begingroup$ A mere replacement of integer variables with their binary equivalents will likely have no effect (the model could be solved a little faster or slower due to the change in the branch and bound search tree). If you could utilize binary variables (e.g., use them to derive valid inequalities, etc, as mentioned in the accepted answer to this question) then it might help to use binary variables. $\endgroup$
    – rasul
    Commented Jul 13, 2021 at 11:16
  • $\begingroup$ if you post the whole formulation it is easier to judge $\endgroup$
    – user3680510
    Commented Jul 13, 2021 at 19:34

1 Answer 1

Reset to default
2
$\begingroup$

There are multiple ways to express a finite interval of integers using boolean variables. A different encoding would be the logarithmic one

$$\sum_{i=0}^{\left \lceil{\log_2(10)}\right \rceil } 2^i\tilde{x}_i \text{ subject to } \sum_{i=0}^{\left \lceil{\log_2(10)}\right \rceil } 2^i\tilde{x}_i \leq 10$$

You can come up with many such encodings and in general the answer is, it depends try it out. In general i would not suspect this to yield better relaxation. What you are doing by introducing this binarization of your variables is that you make branching decisions for the solver (or rather change the space of branching decisions). It could be that your branching decisions are superior to the ones a Mixed Integer solver would pick. In general i would think a pure cutting planes based MILP solver would suffer from your proposed reformulation and since presolving also become harder due to the non-standard input format you might see a drop in performance when using a MILP solver, however such a binarized MILP problem could then be solved using MaxSAT or Pseudoboolean optimization which are a different solver technology and maybe yield performance benefits.

You might also consider initial assignments that break symmetries, experimenting with solver parameters, different solvers (look into Neos Server where you can test different solvers) or consider whether you actually need the global optima.

Improve this answer
$\endgroup$

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.