# Converting linear BIP constraints into convex hull

Given a linear BIP $$\text{Minimize}\;\;\;c^Tx$$ $$\hspace{6.5mm}\text{Subject to}\;\;\;Ax\leq b$$ $$\hspace{38mm}x\in\{0,1\}^n$$

We can in theory convert the constraints to the convex hull constraint $Hx\leq d$ which allows us to perform a linear relaxation and find the solution to the linear BIP that way. Is there an efficient way to find this convex hull and put it in the aforementioned form?

I don't think such a method exists. 3-SAT is polynomial-time reducible to integer programming.. If you could find the integer hull (i.e., convex hull of the integer feasible set) in polynomial time in the general case, you could solve the LP efficiently using a polynomial time algorithms (for instance, an interior point method) and obtain an optimal solution to the ILP, which in turn would give you a polynomial time solution to 3-SAT. We know that 3-SAT is in NP, so unless P = NP (which is unlikely), no such efficient algorithm exists.

The only algorithm I'm vaguely aware of involves solving an exponential number of auxiliary LPs to determine the extreme points of the set. The exponential number arises from noting that an $n$-cube has $2^{n}$ vertices.

• quick question, don't you want the other direction, that 3-SAT is reducible to ILP? Jun 19 '15 at 20:56
• Yes, you do. I'll correct the post. Jun 19 '15 at 21:46