Could someone please comment and answer on the complexity of purely binary linear programming (BLP) and mixed-integer linear programming (MILP)?

In MILP, we have both binary and continuous variables while in BLP we have only binary variables.

From the complexity perspective, which one is easier to solve? I believe both are NP-hard problems.

Do the mixed binary and continuous variables make it harder to solve?

  • 3
    $\begingroup$ from a theoretical point of view, BLP and MILP are equally hard; for some practical considerations you might wish to compare to question or.stackexchange.com/questions/3209/… $\endgroup$ Jan 8 '20 at 23:37
  • $\begingroup$ You can think of a pure integer program (IP) as a special case of a mixed integer program (MIP) (That is, an IP is a MIP with zero continuous variables). Thus, from a complexity perspective, MIP is at least as hard as IP. $\endgroup$
    – Sune
    Jan 10 '20 at 7:32
  • $\begingroup$ @Sune, how about this "IP is at least as hard as MIP"? $\endgroup$ Jan 10 '20 at 9:06

Any (M)ILP can be transformed to an equivalent (M)BLP.

There are multiple methods to do so, some described in this book.

The pure discrete problems are NP-hard just like their mixed integer cousins.

One method is to replace integers by a sum of binary variables per integer, the cardinality of which depends on each integer's span.

In practice, BLPs tend to be slightly easier to solve because binaries allow us to take many algorithmic shortcuts.

Mixed-integer/mixed-binary problems are of the same complexity. In practice, they are often harder to solve because we can't use the same reformulations that apply to pure discrete problems, and the complexity of branching on continuous variables is much worse than creating branch-and-bound trees of discrete variables.

Note however that "harder" here is ambiguous and should be taken with a grain of salt. A problem with 49,999 continuous variables and 1 binary is much easier to solve than a problem with 50,000 binaries.


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.