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
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?
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.
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.
