我认为不存在这样的方法。3-SAT 是多项式时间可简化为整数规划。如果在一般情况下您可以在多项式时间内找到整数壳（即整数可行集的凸壳），则可以使用多项式时间算法有效地求解 LP （例如，内点法）并获得 ILP 的最优解，这反过来会给你一个 3-SAT 的多项式时间解。我们知道 3-SAT 在 NP 中，所以除非 P = NP（这不太可能），否则不存在这种有效的算法。

我隐约知道的唯一算法涉及求解指数数量的辅助 LP 以确定集合的极值点。指数数源于注意到一个立方体有个顶点。$n$$2^{n}$