9

My original problem is an MILP. I make it an LP by relaxing the integer variables.

Can someone please comment on the complexity, solvability and optimality of MILP and LP problems, in general?

Is there a guarantee that a given MILP can be solved optimally?

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
KGM
  • 2,265
  • 7
  • 23

2 Answers2

11

LP can be solved in polynomial time (both in theory and in practice by primal-dual interior-point methods.)

MILP is NP-Hard, so it can't be solved in polynomial time unless P=NP. However, MILP can certainly be solved in exponential time by branch and bound.

Brian Borchers
  • 801
  • 6
  • 12
5

MIP are NP-hard, meaning that in general we don't know of a polynomial-time algorithm for solving MIPs. Note that this statement does not mean that "every MIP is NP-hard" but "solving every MIP in polynomial time is NP-hard". Indeed, there are special cases of MIP problems for which we do have fast algorithms e.g. MIP for which the constraint matrix is TUM (totally unimodular matrix), then it can be relaxed into the linear program, which can be solved in polynomial time.

Antarctica
  • 2,917
  • 15
  • 34