BIP with additional constraints
Constraints
If investment 2 is made, then investment 4 must also be made：
it means: if
If investment 1 is made, then investment 3 cannot be made,
it means: if
0-1 Knapsack Problem
Integer Knapsack Problem
Assignment problem
Set covering problem
注意这里是任意i和任意j都满足。
Traveling salesman problem
注意：因为我们并不知道在求解时，哪个子集 S 会形成独立的小圈(subtour)。
为了防止任何这种情况出现， 我们必须“对所有可能的 S”都强制加上限制条件。
Brute Force
The Knapsack and Covering Problems
设 (
这是一个特殊例子，不是背包问题的通式，而是为了说明：
意思是：
背包容量刚好等于所有物品总体积的一半。
这样做的好处是——一半一半的结构很对称、便于证明：
对任意子集 (S)，它与其补集 (
) 的总体积一正一反，刚好在 (b) 的两边。
补集关系推导（关键逻辑）
写出体积总和：
于是得到：
这说明：
对任意一个子集 (S)，要么它满足背包约束（可行），要么它的补集 (S^c) 满足约束（不可行）。
所以每一对子集 ((
这就建立了“配对”思想。
三、由配对思想推出至少有 (2^{n-1}) 个可行解
我们知道所有子集共有 (2^n) 个。
如果把它们分成互补对子：
每对只算一次，总共有：
而每对中至少有一个满足约束 (
所以我们得到结论：
Graphical method
Divide and Conquer
