$$ min \hspace{3mm}C^TX\\ s.t. \hspace{3mm} AX\leq B $$
위 LP에 $x_j \in Z, j \in D$ 추가하면 I.P. integer programming이 됨.
IP 를 LP relaxation으로 풀어서 무조건 optimal하지 않음
high dim으로 갈수록 error 커짐
NP-hard : Any problem in NP can be reduced to an NP-hard problem in polynomial time
LP는 class of convex optimization임