零一规划

零一规划（binary programming，也写作0-1规划）用取值为零或一的变量表达是否选择、是否启动、是否分配等决策。本文讨论目标和约束均为线性的情形；如果还包含连续变量，便属于混合二元规划，若含非线性表达式，则又需相应的非线性求解方法。

设有三个可选项目 $A,B,C$，收益分别为八、七、五个单位，投入分别为二、三、二个单位，预算为五。项目 $A,B$ 不能同时实施，$C$ 又必须以 $A$ 已实施为前提。用 $a,b,c\in \{0,1\}$ 表示三项选择，模型为 $$\begin{array}{cc}max& 8a+7b+5c,\\ 2a+3b+2c& \le 5,\\ a+b& \le 1,\\ c& \le a.\end{array}$$ 收益单位和投入单位可以不同，约束只将同类资源相加。这些数据为教学设定，不表示真实项目的收益预测。

逻辑关系对应的线性约束

对二元变量，$c\le a$ 恰好表达“选择C就必须选择A”：当 $c=1$ 时只能 $a=1$；当 $c=0$ 时，$a$ 仍可零可一。它并没有表达反向的“有A就必须有C”。$a+b\le 1$ 排除的是同时取一，仍允许两个都不选。

若希望恰选一个，可写 $a+b=1$；若只要求至少选一个，则是 $a+b\ge 1$。把“且”写成新的二元变量 $z=ab$，可用以下线性式替代乘积： $$\begin{array}{cc}z& \le a,z\le b,\\ z& \ge a+b-1,z\ge 0.\end{array}$$ 验证只需分两类：若任一个输入为零，前两式迫使 $z=0$；若两者都为一，第三式迫使 $z\ge 1$，再由上界得 $z=1$。即使把 $z$ 声明为连续变量，这些界在 $a,b$ 已为二元时也会迫使正确取值。

四个可行方案的比较

原先八种零一组合中，依赖关系和互斥关系只留下四种：

选择(a,b,c)	投入	收益
(0,0,0)	0	0
(0,1,0)	3	7
(1,0,0)	2	8
(1,0,1)	4	13

四者均未超出五的预算，故最优是选择 $A,C$，总收益十三。单纯按收益逐项从大到小选择，会先取A，再想取B，却忽略了互斥要求；模型中的每一种限制都要一并检查。

箭头表示先决逻辑，不表示支付或物料流。选择A并不强迫选择C；预算仍须另行检查。

小规模枚举及其正确性

下面的函数枚举全部二元向量，然后检查预算、先决关系与互斥关系。每个合法选择在枚举中恰好出现一次，因此保留已检查方案中的最大收益，就得到全局最优；这项证明来自覆盖完整搜索空间，不来自样例跑出了十三。

输入收益、非负投入及预算、依赖对与互斥对；依赖对 (i,j) 表示选择i必须选择j。函数不改输入，返回最优收益和选择向量。设有 $n$ 个项目、$L$ 对逻辑限制，时间 $O(2^n(n+L))$，额外空间 $O(n+L)$；这是小规模校验器。

Python 3

from itertools import product
import math

def binary_projects(values, costs, budget, requires=(), excludes=()):
    v, c = tuple(values), tuple(costs)
    dep, exc = tuple(requires), tuple(excludes)
    n = len(v)
    if len(c) != n or any(not math.isfinite(x) for x in v + c + (budget,)):
        raise ValueError("matching finite data required")
    if budget < 0 or any(x < 0 for x in c):
        raise ValueError("nonnegative costs and budget required")
    if any(type(i) is not int or not 0 <= i < n
           for pair in dep + exc for i in pair):
        raise ValueError("invalid project index")
    if any(len(pair) != 2 for pair in dep + exc):
        raise ValueError("each relation must contain two indices")
    best_value, best = -math.inf, None
    for x in product((0, 1), repeat=n):
        if sum(c[i] * x[i] for i in range(n)) > budget:
            continue
        if any(x[i] > x[j] for i, j in dep):
            continue
        if any(x[i] + x[j] > 1 for i, j in exc):
            continue
        value = sum(v[i] * x[i] for i in range(n))
        if value > best_value:
            best_value, best = value, x
    return best_value, best

print(binary_projects([8, 7, 5], [2, 3, 2], 5,
                      requires=[(2, 0)], excludes=[(0, 1)]))
# (13, (1, 0, 1))

变式。 预算从五降为三，组合 $(1,0,1)$ 超支；其余三个方案中，A的收益八高于B的七，所以最优只选A。没有项目时，空向量是合法选择，收益为零。零一限制不能用“先求连续解、最后逐项四舍五入”取代：约束 $2x\le 1$ 下的松弛点 $x=1/2$ 向上舍入后就会违反预算。