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$
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$
  • $\begingroup$ quick question, don't you want the other direction, that 3-SAT is reducible to ILP? $\endgroup$ – Thoth Jun 19 '15 at 20:56
  • $\begingroup$ Yes, you do. I'll correct the post. $\endgroup$ – Geoff Oxberry Jun 19 '15 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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