离散优化的目标：当然不是求解 NP-难问题

1. 尽可能把计算时间的指数爆炸推远，以让计算适当规模的问题成为可能

   

2. 降低标准，近似求解。

离散优化的例子

• 肾脏移植。

  • 每个节点表示一组人：一个需要接受肾脏的人（接受者）以及他愿意捐赠肾脏的亲属（捐赠人）。
  • 边表示起点捐赠人的肾脏能够适配给终点的接受者。
  • 我们需要用回路连接起尽可能多的节点，且保证这些节点有且仅有一入度，有且仅有一出度。

  

• 电网修复。

  • 左边是电网抢救工作的路线图（需要组织），右边是电力随时间恢复的图解。要让 Blackout Size 最小化。

  

离散优化问题的分类

• Optimization Problem 优化问题：可以描述为「$\min (\max) \, f(x), \, {\rm s.t.} \, x \in S$」，$S$ 可能是由一系列约束条件所描述的。
• Constraint Satisfaction Problem 约束满足问题：可以描述为「找到一个 $x \in S$」，$S$ 通常是由一系列约束条件所描述的。
• Decision Problem 判断问题：一个例子是「是否存在 $x \in S$，使得 $f(x) \ge M$」？
• Counting Problem 计数问题：求解满足 $x \in S$ 的可行解的数量，也就是求 $|S|$。