14
$\begingroup$

When I have to write the formulation of an IP, I usually have the choice between writing $i\times j$ binary variables with two indices such as $ x_{i,j} $ or, writing $j$ integer variables $x_i$.

Is it better to use only binary variables but with a higher number of variables or to use fewer integer variables? Does a solver work better with binary variables?

I personally think that the stronger limitation of a variable is the number of variables so I would choose the solution with fewer integer variables. However, I would like to confirm that.

Thank you in advance for your advice! (PS: Tell me if my question is not clear)

Improve this question
$\endgroup$

2 Answers 2

Reset to default
20
$\begingroup$

I learned very early (this may not be generally true) that I should always prefer binary over integer variables. A reason is that from binary values you can infer logical information, branching on a binary variable fixes its value (=reduces the model) etc.

I would go even further. It may be better to have more variables. Why? Of course, this depends on the formulation, but more variables often means that you have more possibilities to express yourself, that may imply more opportunities to derive cuts etc. I personally think that it is easier to formulate the constraints (think even only of avoiding that two integer variables have the same value, and how easy it is with binary variables). All this is not computationally supported here by myself, but I am sure that someone could. I, for one, use as many variables as I can, I introduce variables which carry a lot of meaning, represent entire partial solutions, configurations, subsets, etc. This typically gives me stronger relaxations. You may need a special algorithm to deal with a larger number of variables (like column generation).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you very much for your answer! $\endgroup$
    – JonathanZ
    Dec 18, 2019 at 21:25
4
$\begingroup$

If you have a question about what's faster for your work cases, try both on your system. There's quite a variety in simplex solvers, especially when you're talking about integer programming. If you can convert it, a smart enough system can convert it, and probably more optimally than you can without system details. Testing the system is the only way to figure out what's faster on your system.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I agree on "you have to try it", but using "simplex" and "integer programming" in one sentence makes my wonder what you try to say. Same goes for "more optimal" and what the "converstion" should be about. Can you please elaborate? $\endgroup$
    – Marco Lübbecke
    Dec 19, 2019 at 18:44
  • $\begingroup$ @MarcoLübbecke As per or.stackexchange.com/questions/176/… , integer programming solvers generally use a simplex LP solver with branch-and-bound (or -and-cut) to solve the problem. $\endgroup$
    – prosfilaes
    Dec 20, 2019 at 2:43
  • $\begingroup$ @MarcoLübbecke The OP said that there was the choice between integer variables and Boolean variables; if so, then a smart enough automated system can see that and make the conversion. And that same system will have a good idea when splitting an integer variable into multiple Boolean variables becomes too much, which might depend on other parts of the system or how the internal simplification of the problem went. $\endgroup$
    – prosfilaes
    Dec 20, 2019 at 2:59
  • $\begingroup$ the simplex algorithm is one algorithm to solve the LPs, yes, but how/why would it be affected by using either integer or binary variables? And the "splitting" of the variables (binary expansion) is typically NOT what makes the difference between integer and binary variable models, but the variables hav different meanings. In general, this is not automatically reformulated. $\endgroup$
    – Marco Lübbecke
    Dec 20, 2019 at 6:58
  • $\begingroup$ @MarcoLübbecke If you're comparing x_i with x_i1, x_i2..., as per the OP, this is something that could be done automatically. I'm curious as to your source of information about what is automatically reformulated; certainly I expect that CPLEX and other expensive tools do dark magic on their problems. Meanings are irrelevant if the answers are interconvertable. $\endgroup$
    – prosfilaes
    Dec 20, 2019 at 10:53

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.