整数线性规划 很多组合优化问题都能通过整数线性规划表示出来 最大二分图匹配： ·max∑eEE CeXe 。 ∑e∈d)xe≤1 VvEV xe E(0,1} Ve EE 最大独立集： max∑vEVCvXv xu+xv≤1 Vuv∈E 包括Np-hard问题！ xvE{0,1} 15 整数线性规划 很多组合优化问题都能通过整数线性规划表示出来 最大二分图匹配： • max ∑P∈R �P�P • ∑P∈S T �P ≤ 1 • �P ∈ {0,1} 最大独立集： • max ∑T∈U �T�T • �! + �T ≤ 1 • �T ∈ {0,1} 15 ∀� ∈ � ∀� ∈ � ∀�� ∈ � 包括NP-hard问题！