整数线性规划IntegerLinearProgramming

求解整数线性规划问题的分支定价算法摘要本文简要介绍求解大规模整数线性规划问题的分支定价（Branch-and-Price）精确算法,该类算法可用于求解含有大规模变量的整数线性规划问题(Integer Linear Program，ILP)或混合整数线性规划问题(Mixed Integer Linear Program，MILP)。

分支定价算法综合了列生成(Column Generation)和分支(Branching)策略。

列生成算法用于求解含有大规模变量的线性规划问题。

分支定价算法在每个分支节点处采用列生成策略求得对应松弛问题的最优解。

由于列生成策略大大降低了松弛问题的规模,可在很大程度上降低求解时间。

本文主要对分支定价算法的基本思想，执行步骤及关键问题进行详细的介绍。

关键词整数线性规划分支定价列生成算法一引言整数规划(Integer Programming,IP)问题最早出现在20世纪50年代,现在整数规划适用于工程、电子信息、工程管理和经济等领域。

整数规划是带有整数变量的最优化问题,即最大化或最小化全部或部分变量为整数的多元函数受约束于一组等式或不等式条件的最优化问题。

有时候我们求解的结果要求我们取整数,但是有时候我们求得的解是小数,而且当我们把小数的解四舍五入化为整数，发现化整后的解并不是可行解，或虽是可行解,但不是最优解,因此,对求解最优整数解的问题,我们称之为整数规划。

对于小规模的整数规划问题,其求解通常采用分支定界算法,但当问题规模特别大时,分支定界算法的执行效率会很低,有时甚至得不到可行解。

因此研究者们致力于寻找求解大规模整数规划问题更好的方法。

Barnhart[1]等人研究了求解整数线性规划问题的分支定价算法(Branch-and-Price),该类算法可用于求解含有大规模变量的整数线性规划问题或混合整数线性规划问题,其核心思想是在分支定界的基础上采用列生成(Column Generation)策略。

数学建模常用方法数学建模是利用数学工具和方法来研究实际问题，并找到解决问题的最佳方法。

常用的数学建模方法包括线性规划、非线性规划、动态规划、整数规划、图论、最优化理论等。

1. 线性规划（Linear Programming, LP）: 线性规划是一种在一定约束条件下寻找一组线性目标函数的最佳解的方法。

常见的线性规划问题包括生产调度问题、资源分配问题等。

2. 非线性规划（Nonlinear Programming, NLP）: 非线性规划是指当目标函数或约束条件存在非线性关系时的最优化问题。

非线性规划方法包括梯度方法、牛顿法、拟牛顿法等。

3. 动态规划（Dynamic Programming, DP）: 动态规划方法是一种通过将复杂的问题分解成多个子问题来求解最优解的方法。

动态规划广泛应用于计划调度、资源配置、路径优化等领域。

4. 整数规划（Integer Programming, IP）: 整数规划是一种在线性规划的基础上，将变量限制为整数的最优化方法。

整数规划常用于离散变量的问题，如设备配置、路径优化等。

5. 图论（Graph Theory）: 图论方法研究图结构和图运算的数学理论，常用于解决网络优化、路径规划等问题。

常见的图论方法包括最短路径算法、最小生成树算法等。

6. 最优化理论（Optimization Theory）: 最优化理论是研究寻找最优解的数学方法和理论，包括凸优化、非凸优化、多目标优化等。

最优化理论在优化问题建模中起到了重要的作用。

7. 离散数学方法（Discrete Mathematics）: 离散数学方法包括组合数学、图论、概率论等，常用于解决离散变量或离散状态的问题。

离散数学方法在计算机科学、工程管理等领域应用广泛。

8. 概率统计方法（Probability and Statistics）: 概率统计方法通过对已有数据进行分析和建模，提供了一种推断和预测的数学方法。

概率统计方法在决策分析、风险评估等领域起到了重要的作用。

§3.1 整数线性规划整数线性规划( Integer Linear Programming ，简记为 ILP )⎪⎪⎩⎪⎪⎨⎧⊂∈∈≥=},,2,1{,0..min n J i I x x b Ax t s x c i T Λ （3.1.1）其中，},2,1,0{Λ=I<1>若 },,2,1{},1,0{n J I Λ==，则称（3.1.1）为0-1规划问题；<2>若 J 是 },,2,1{n Λ的非空真子集，则称（3.1.1）是混合整数线性规划问题；<3>若 },,2,1{n J Λ=，则称（3.1.1）是纯整数线性规划问题。

1、整数线性规划问题举例例 3.1.1 某部门在今后五年中有 B 万元的资金可以用于投资，有 )2(≥n n 个可以考虑的投资项目。

假定每个项目最多投资一次，其中第 j 个项目需投资金额为 j b 万元，将会获得的利润为 j c 万元，问应如何选择项目，才能使获得的总利润最大？解：设投资决策变量为n j j j x j ,,1,0,1Λ=⎩⎨⎧=个项目，决定不投资第个项目，决定投资第，设获得的总利润为 z ，则⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧==≤<=∑∑==n j x Bx b t s x c z j n j j j n j jj ...,2,1;010..max 11或 （3.1.2） 问题（3.1.2）是一个0-1规划。

01或=j x 这个约束可以用一个等价非线性约束0)1(=-j j x x来代替它。

因而变量限制为整数本质上是一个非线性约束。

例 3.1.2 某建筑公司承包两种类型宿舍。

甲种宿舍每幢占地面积为 31025.0⨯平方米；乙种宿舍每幢占地面积为 3104.0⨯平方米。

该公司已购进 3103⨯平方米的建筑用地。

计划要求建甲种宿舍不超过8幢，乙种宿舍不超过4幢。

建甲种宿舍每幢可获利10万元，建乙种宿舍每幢可获利20万元。