1. 整数规划入门为什么我们需要ILP第一次接触整数规划Integer Linear Programming, ILP是在研究生时期的运筹学课上。当时教授给了一个经典案例某工厂需要决定生产多少台设备要求必须是整数。用常规线性规划求解后得到生产3.7台的结果全班哄堂大笑——这就像让你把蛋糕切成0.3块一样荒谬。整数规划的本质特征在于决策变量必须取整数值。这种要求在实际中非常普遍物流配送需要整数辆卡车人员调度需要整数个员工芯片设计需要整数个晶体管我处理过的真实案例中最典型的是某电商的仓库选址问题。当决策变量表示是否在某地建仓时只能取0或1这就是0-1规划。直接用线性规划求解会得到建0.6个仓库的荒唐结果这时候就必须使用整数规划方法。与线性规划相比整数规划有三大独特性质解的不连续性最优解可能就在邻近整数点但简单的四舍五入会导致约束 violation违反约束计算复杂度飙升从多项式时间直接跳转到NP-Hard最优解不可预测线性松弛解与整数最优解之间可能毫无关联% 典型整数规划问题示例 f [-3; -2]; % 目标函数系数 A [2 3; 2 1]; % 约束矩阵 b [14; 9]; % 约束右端项 lb [0; 0]; % 变量下界 [x,fval] intlinprog(f,[1,2],A,b,[],[],lb);这个简单例子中如果不加整数约束最优解是(3.25, 2.5)加上整数约束后最优解变为(4,1)。两者目标值相差约5%在实际项目中可能就是数百万的利润差距。2. 分支定界法像侦探一样搜索最优解去年帮一家制造企业优化生产计划时我深刻体会到了分支定界法的精妙。他们需要安排5条产线的生产批次每个批次必须完整执行不能半途而废。面对可能的解空间达到10^20量级分支定界法在2小时内就找到了最优解。分支定界法的核心思想是分而治之松弛先暂时忽略整数约束求解线性规划分支对非整数解变量x_i创建两个子问题x_i ≤ ⌊x_i⌋ 和 x_i ≥ ⌈x_i⌉定界维护当前最优整数解剪掉目标值更差的分支实际操作中有几个关键技巧变量选择策略我习惯优先分支小数部分最接近0.5的变量节点选择深度优先搜索更容易找到可行整数解提前终止当差距小于1%时商业场景通常可以接受% 分支定界法MATLAB实现示例 function [x_opt, f_opt] branch_and_bound(f, A, b, intcon) % 初始化 [x, fval] linprog(f, A, b, [], [], zeros(size(f))); active_nodes struct(x,x,fval,fval,constraints,{}); f_opt inf; while ~isempty(active_nodes) % 选择节点 node active_nodes(1); active_nodes(1) []; % 检查界限 if node.fval f_opt continue; end % 检查整数性 fractional abs(round(node.x(intcon)) - node.x(intcon)) 1e-6; if ~any(fractional) if node.fval f_opt f_opt node.fval; x_opt node.x; end continue; end % 分支 idx find(fractional, 1); x_val node.x(idx); % 创建左分支(x floor(x_val)) new_A [A; zeros(1,length(f))]; new_A(end,idx) 1; new_b [b; floor(x_val)]; [x_left, f_left] linprog(f, new_A, new_b); % 创建右分支(x ceil(x_val)) new_A(end,idx) -1; new_b(end) -ceil(x_val); [x_right, f_right] linprog(f, new_A, new_b); % 添加新节点 if ~isempty(x_left) active_nodes(end1) struct(x,x_left,fval,f_left,constraints,{new_A, new_b}); end if ~isempty(x_right) active_nodes(end1) struct(x,x_right,fval,f_right,constraints,{new_A, new_b}); end end end在实际项目中我发现MATLAB的intlinprog函数已经高度优化。对于中等规模问题变量数1万直接使用它比自编算法更可靠。但对于特定结构的问题定制化的分支策略可以提升10倍以上的速度。3. 割平面法用数学手术刀修剪解空间第一次成功应用割平面法是在解决一个供应链网络设计问题时。客户有50个潜在仓库选址和200个需求点传统的分支定界法需要超过8小时。引入割平面后求解时间缩短到47分钟——这让我真正理解了好的算法就是生产力的含义。割平面法的精髓在于逐步添加约束称为割平面切除非整数最优解区域同时保留所有可行整数解。就像雕刻家去掉多余的石料最终露出完美的雕像。常用的割平面类型包括Gomory割从单纯形表的最后一行生成混合整数舍入割对约束进行组合和舍入覆盖割适用于0-1规划的特殊割平面% Gomory割平面算法实现框架 function [x_opt, f_opt] gomory_cut(f, A, b, intcon) while true [x, fval] linprog(f, A, b); % 检查整数性 if all(abs(x(intcon) - round(x(intcon))) 1e-6) x_opt x; f_opt fval; return; end % 选择非整数行生成割平面 [~, idx] max(abs(x(intcon) - round(x(intcon)))); row A(idx,:); fractional row - floor(row); % 添加割平面 new_constraint [fractional, -1]; % 引入松弛变量 A [A, zeros(size(A,1),1); new_constraint(1:end-1), 1]; b [b; -fractional(end)]; end end在实际应用中我发现几个提升效率的技巧割平面选择优先添加最违反的割平面即小数部分最接近0.5的割平面池积累多个割平面再批量添加减少迭代次数混合策略与分支定界结合形成Branch-and-Cut算法有个有趣的案例在解决某航空公司机组排班问题时单纯用割平面法在200次迭代后仍未收敛。后来我们加入问题特定的有效不等式如航班衔接约束仅需15次迭代就找到了最优解。4. MATLAB实战intlinprog的高级技巧经过多年使用MATLAB解决ILP问题我总结出一些教科书上找不到的实战经验。这些技巧曾帮助我将求解时间从小时级缩短到分钟级特别是在处理大规模问题时效果显著。intlinprog的核心参数调优options optimoptions(intlinprog,... Heuristics,advanced,... % 使用高级启发式 CutGeneration,intermediate,... % 中等强度的割平面 IntegerPreprocess,advanced,... % 加强预处理 LPPreprocess,basic,... % 基本LP预处理 RootLPMaxIter,10000,... % 根节点LP最大迭代次数 MaxTime,3600); % 最大运行时间(秒)常见问题排查指南模型不可行检查lb和ub是否合理用linprog先求解松弛问题逐步添加约束定位问题来源求解速度慢尝试不同的BranchRule如maxpscost调整NodeSelection为mininfeas使用display参数监控求解过程内存不足设置MaxNodes限制搜索空间启用CutGeneration,none关闭割平面考虑分解算法或启发式方法% 生产计划优化实例 products {手机,平板,笔记本}; profit [300; 450; 600]; % 单位利润 machine_hours [0.5, 0.8, 1.2; % 装配线 0.3, 0.0, 0.6]; % 测试线 capacity [240; 120]; % 每周可用工时 % 构建模型 f -profit; % 最大化利润 A machine_hours; b capacity; lb zeros(3,1); intcon 1:3; % 求解 [x, fval] intlinprog(f, intcon, A, b, [], [], lb); production round(x); % 确保整数解在最近的一个智能仓储项目中通过合理设置AbsoluteGapTolerance为50即允许50元的绝对误差我们将2000个SKU的补货问题求解时间从3小时降到了22分钟而最终方案的成本差异不到0.1%。这种权衡在实际业务中往往非常值得。对于超大规模问题变量数10万我通常会采用以下策略分解算法将问题按时间/空间分解为子问题启发式初始化用贪婪算法提供初始可行解并行计算利用UseParallel选项加速模型简化剔除明显不活跃的变量和约束