Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
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?
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.
