Mixed integer problem

MIP by its nature is NP-hard.

Solving an MIP typically has a convex phase (root LP relaxation, adding cutting planes), followed by a branch-and-bound phase. The former is efficient, whereas the latter is not. Its difficulty is inherent, regardless of which solver you go with.

In practice it’s highly problem-dependent. Some problems, despite might look large, may be efficiently solved, whereas some are not.

It is easy to create an MIP instance that let Gurobi struggle in its branch-and-bound phase. e.g.

Integer variables should be added only when they are necessary.


By the way, @ufechner7 your title is too big, that attracts everyone to take a look.

1 Like