I am working on a problem in which I have to solve 0-1 linear programs, that is linear programs where some of the variables are binary, i.e. either 1 or 0.

Lets say I have a fixed number of $n$ variables in my program of which $k \leq n$ are binary. The other $n-k$ variables are continuous. My question is: What can be said about the efficiency of solving these problems with respect to $k$? I know that 0-1-programming is NP-hard, but does it make a difference whether $k$ is small or large?

In my problem setting, I can somewhat modify the parameter $k$, i.e. the number of binary variables. Is it recommendable to lower them if possible ($k=0$ is impossible)? If so, why?

Thanks in advance

P.S.: If someone could point me to a paper discussing this, I'd happily download it.

  • $\begingroup$ k binary variables cannot be worse than a factor $2^k$ obviously, since you can just try out all possible values. A good solver will usually do better. (I was assuming that the other variables are not restricted to integer values) $\endgroup$ – gnasher729 Jul 13 '17 at 17:26
  • 2
    $\begingroup$ Are the other $n-k$ variables integral? $\endgroup$ – Rodrigo de Azevedo Jul 14 '17 at 12:36

If the other variables are integer variables

This is still NP-hard, even when $k=0$, for the same reason that integer programming is hard.

As for whether lowering the number of binary constraints will help in practice, that depends, and usually the only way to know is to try it. It will depend on what the price of doing that is, as well as depend on the behavior of your ILP solver (which can sometimes be hard to predict).

I would expect that binary variables are harder to deal with than integer variables with a larger range. In particular, if we have an integer variable whose values are in the range $\{0,1,2,\dots,r\}$, then I would expect that the smaller $r$ is, the harder the problem is. Heuristically, the larger the value of the integer variable is, the better it can be approximated with a continuous variable (not restricted to integers), so the closer it comes to linear programming. A standard strategy for ILP solvers is to solve the linear program without the integer constraints, then fine-tune the solution somehow to make everything an integer (e.g., round to the nearest integer). We might hope that the larger the integers, the less error this process will introduce. So, binary variables might be a lot harder than integer variables whose value will be large and whose range of plausible values is large. This is not a hard-and-fast rule; just a rule of thumb to help you think about formulating your problem as an integer problem.

As always, the ultimate answer is to try it and see.

See also https://cstheory.stackexchange.com/q/16530/5038 and https://cstheory.stackexchange.com/q/29317/5038. The operations research community studies what properties of ILP problems tend to be solvable more efficiently with existing ILP solvers (as "rules of thumb" and heuristics).

If the other variables are continuous variables

Then yes, the fewer binary constraints, the faster the ILP solver probably will be. With no binary constraints (or integrality constraints), this becomes linear programming, which can be solved in polynomial time and for which there are efficient algorithms. It's the binary constraints that make the problem hard. The more binary constraints you have, the harder things can get.

| cite | improve this answer | |
  • $\begingroup$ Thanks a lot for your answer. Regarding your first sentence: Maybe I have not been clear enough, but if $k=0$ then the problem has no binary variables and thus is an LP, which is solvable in polynomial time. $\endgroup$ – Doc Jul 14 '17 at 10:59
  • $\begingroup$ @Doc, OK. Can you edit the question to clarify that? I've edited my answer to address that case. $\endgroup$ – D.W. Jul 14 '17 at 13:27
  • $\begingroup$ Sure, sorry for being unclear. Thanks for your help $\endgroup$ – Doc Jul 15 '17 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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