IPCO重点

2026-01-05

数学

4.5k 词

formulate a linear problem

这道题目要求我们将逻辑条件转化为整数规划（Integer Programming）中的线性约束条件。

(ii) Project 4 must be selected if either project 1 or project 2 is selected
含义：如果选择了项目1 或者选择了项目2，那么必须选择项目4。

写法一（推荐，更清晰）：

(解释：如果，则必须为1；同理。)
写法二（合并写法）：

(解释：左边最大可能是2。如果，左边必须是0；如果，左边可以是0, 1或2，即允许选1或2。)

(iii) Project 5 is selected if and only if at least one of the projects 1 and 3 is selected
含义： 这是一个“当且仅当”（if and only if）的条件，包含两个方向的逻辑：

如果选了1或3（或都选），则必须选5。
如果选了5，则意味着必然选了1或3其中至少一个。
方向（至少一个被选则选5）：

(如果或为1，左边大于0，强制为1。)
方向（选了5则至少有一个被选）：

(如果和都是0，左边必须是0。)

(iv) Project 5 is selected if and only if both the projects 1 and 3 are selected

如果1和3同时被选，则必须选5。
如果选了5，则1和3必须都被选中。
方向（两个都选则选5）：

(如果，左边为，强制，即。其他情况左边，对无限制。)
方向（选了5则两个都必须选）：

(如果，则和都必须，即都为1。)

(v) Project 5 is selected if and only if exactly one of the projects 1 and 3 is selected
含义：这是逻辑“异或”（XOR）。只有当和的状态不同（一个选一个不选，即和为1）时，才为1。如果两个都不选（和为0）或者两个都选（和为2），必须为0。

题目提示允许引入一个辅助变量（auxiliary variable）。
判断关键词：

“Exactly one”（恰好一个）：这是最明显的标志。
“Either A or B, but not both”（要么A要么B，但不能同时）：这是异或的标准定义。
互斥且必须选其一：如果题目说两个项目中必须选一个，且不能都选，也不能都不选。

约束条件：
引入一个二进制辅助变量。

我们可以利用等式约束来完美表达这个关系：

解析这个等式为何有效：

情况1：都不选 () Sum = 0。
等式变为。由于都是非负整数，唯一解是。(符合：不选5)
情况2：只选一个 ( 或反之) Sum = 1。
等式变为。由于只能是偶数(0或2)，要等于1，必须且。所以。(符合：选5)
情况3：都选 () Sum = 2。
等式变为。
- 如果，则（不可行，因为是二进制）。
- 如果，则，解得。(符合：不选5)
  因此，这就完美满足了“恰好选一个时选5，否则不选5”的要求。

Dynamic programming

例题

下面用表格 + 回溯”的格式，把图一这个 0-1 背包做完。

问题数据（按物品 (r=1,2,3) 编号）

价值：
重量：
容量：

Initialization（算法初始化的变量）

状态：() = “只考虑前 (r) 个物品、容量为 () 的最大价值”
决策：() = “在状态 (()) 是否选第 (r) 个物品”
初值：对所有 ()，令

DP 递推（与图二一致）

对 r=1,2,3，：

若 ()，则 ()，且 ()；
若 ()，则

并令 () 当且仅当取后者更优（若相等则记作“1/0”，表示两种都可）。

polyhedron

A polyhedron is the feasible region of a system of linear inequalities —
the geometric object that represents all solutions to an LP.

formulation

检验 P 是 set S 的 formulation 要求两步：
1.判断S所有点都在P
2. $（是$

本质就是在证明一个东西P是X的formulation，要求P的整数解等于X的解。

ideal formulation

Integer vertices

convex set

一定是 convex（凸集）。更准确地说，它是一个 仿射子空间 (affine subspace)，而仿射子空间总是凸的。

branch and bound

simplex method and dual simplex method

第一步一定先把 max 改成 min
单纯形表的排版顺序固定
1️ 最上一行是目标行 f
2️ 下面依次是约束行
目标行初始化规则固定
- 目标行写成：()
- 表中系数一律用 (-c)（你强调的这一点我已经锁死）
min 问题的 pivot 规则
- 看 (f) 行
- 最大正数入基
- ratio test 决定出基
Branch and Bound
- LP 松弛：完整 simplex 表
- 加分支约束：直接加到当前最优表
- 出现 (b<0)：dual simplex
- 每一步 pivot 表必须写出来，不跳

vaild inequality

若不等式是型（或等价地希望左边不增），对左边系数用向下取整 ，因为对非负整数变量，，不会破坏“≤”的成立；而此时右边若是常数，为保证整数解成立，要对右边向下取整。
若不等式是 ≥ 型（或等价地希望左边不减），对左边系数用向上取整 ⌈⋅⌉，因为 ⌈a⌉x≥ax，仍保持“≥”有效；而右边为常数时，要对右边向上取整**。

IP problem

IP 问题与ideal formulation的关系：

LP Relaxation

greedy heuristics method（反例：是feasible不是optimal）

一个典型的反例是 0-1 背包问题。假设背包容量为 ( W = 50 )，有三件物品：

物品	重量	价值	单位价值 (v/w)
A	10	60	6
B	20	100	5
C	30	120	4

贪心算法会按单位价值从高到低选择物品，因此依次选 A（10kg）、B（20kg），此时背包剩余 20kg，但 C 需要 30kg 放不下，于是总价值为 (60 + 100 = 160)。
然而最优解是选择 B 与 C（20 + 30 = 50），总价值为 (100 + 120 = 220)，明显更高。

原因在于：贪心算法仅考虑当前单位价值最高的物品，却忽略了整体组合的收益，导致陷入局部最优。这表明贪心法在 0-1 背包问题中不能保证全局最优解。

TU Matrix

Sufficient Condition

证明：

Assume that (i)–(iii) are satisfied but that A is not TU. Let B be a smallest square submatrix of A such that det⁡(B)∉{0,+1,−1}. Then all columns of B contain exactly two nonzero coefficients (why? If B contains a column with a single nonzero entry, B would not be minimal). Because of (iii), adding the rows of B with indices in and subtracting the rows with indices in yields the zero vector, showing that the rows of B are linearly dependent and , which contradicts the choice of B.