1
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ quick question, don't you want the other direction, that 3-SAT is reducible to ILP? $\endgroup$
    – Set
    Commented Jun 19, 2015 at 20:56
  • $\begingroup$ Yes, you do. I'll correct the post. $\endgroup$ Commented Jun 19, 2015 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.