高效求解整数线性规划问题的分支算法

为了提高求解一般整数线性规划问题的效率,提出了一种基于目标函数超平面移动的分支算法。对于给定的目标函数整数值,首先利用线性规划松弛问题的最优单纯形表确定变量的上、下界,然后将变量的上、下界条件加入约束条件中对相应的目标函数超平面进行切割,最后应用分支定界算法中的分支方法来搜寻目标函数超平面上的可行解。通过对一些经典的数值例子的求解计算并与经典的分支定界算法进行比较,结果表明,该算法减少了分支数和单纯形迭代数,具有较大的实用价值。     

整数线性规划的改进分支定界算法

分支定界(B&B)算法是求解整数线性规划(ILP)问题的一种最常用的方法,如何划分问题(分支)和按何种策略选择子问题进行扩展是影响算法效率的两个重要因素.提出了一种改进的分支定界算法,采用伪费用分支策略划分问题,采用深度优先搜索(DFS)策略选择子问题进行扩展,并在Matlab中编程实现.数值实验表明,改进的算法能够有效提高求解效率,当问题规模较大时,改进效果尤其明显.     

加速分支定界算法在化工过程合成中的应用

在化工过程合成中,人们在确定研究系统的最大超结构后,通常采用混合整数非线性规划模型将其表达,而后通过计算机对该模型求解,从而找到最佳的流程结构.然而,近年来出现了1种新的求解过程,称为加速分支定界法(ABB),是在最大结构已知的基础上,采用分支定界法进行求解的思路.该算法克服了传统方法在处理整型变量时出现的麻烦,不需要建立复杂的混合整数非线性规划模型,就可以实现计算机自动寻找最优的过程流程,为快速有效地求解化工过程综合优化问题提供了1种新的途径.本文对分支定界法与加速分支定界法进行了详细比较,证实了ABB算法在实现自动寻找最优流程结构的合理性与可靠性.最后,以生化法制备丁醇、乙醇和丙酮的下游分离提纯为实例,研究了ABB算法在过程优化中的应用.结果表明,该算法克服了传统方法在处理整型变量时出现的麻烦,是1种快速有效地求解化工过程综合优化问题的新途径.     

求解整数线性规划问题的定界阻止算法的改进*

在现有求解整数线性规划问题的定界阻止算法的基础上提出了一种改进。该算法通过目标函数超平面截线性规划松弛问题的有效约束锥而形成一个单纯形;然后,引入一串平行片来切割该单纯形产生更低维的凸多面体;最后,在片上的这些凸多面体上执行阻止搜寻程序。由于单纯形和片上凸多面体的极顶点可以直接通过公式计算,且变量在片上凸多面体上的取值区间更窄,改进的定界阻止算法既方便又高效,这得到了一些经典算例和随机产生的算例的验证。     

连铸-轧制混流生产模式下轧批调度问题的分支-定价算法

研究了连铸——轧制在热装、温装和冷装混流生产模式下的一类新型轧批调度问题.以最小化温装钢坯（热钢锭）缓冷（等待）导致的热能损失和连轧机架切换带来的产能损失为目标,建立了整数规划模型.由于商业优化软件难以在有限时间内直接求得模型的最优解甚至可行解,提出利用Dantzig-Wolfe分解技术将原模型分解为主问题和子问题,采用列生成算法对主问题和子问题进行迭代求解得到原问题的紧下界,最后以列生成算法作为定界机制嵌入分支——定界框架中形成分支——定价算法,执行分支搜索过程以获得整数最优解.本文还从影响分支——定价算法性能的要素出发提出改进策略.针对主问题,提出列生成和拉格朗日松弛混合求解策略来抑制单一列生成算法的尾效应.针对价格子问题,在动态规划算法中提出了基于占优规则和标号下界计算方法来及早消除无效状态空间,加速求解过程.以钢铁企业的实际生产数据和扩展的随机算例进行了数值实验,结果显示所提出改进策略能够突破求解能力的限制,使分支——定价算法在可接受计算时间内求得工业规模问题的最优解.     

结合分支定界法和线性规划的摄像机位姿估计

介绍了一种新的利用对应点估计摄像机位姿的算法。通常情况下,摄像机位姿估计可以转化为一个最优化问题,现有算法将问题转换成一个序列二阶锥规划问题,通过对旋转矩阵所在空间进行分支定界搜索来求取全局最优解。对现有算法进行改进,通过将二阶锥约束松弛为线性约束,提出了一种结合分支定界法和线性规划方法的全局优化算法。该算法不仅能够求得全局最优解,而且算法速度较现有算法提高了一倍以上。最后通过模拟数据和真实数据对该算法进行了验证,结果表明了该算法的准确性和高效性。     

基于分支定界-改进AO~*算法的序贯测试策略优化

针对经典AO*算法在求解序贯测试问题中复杂度太大的难题,提出测试选择与策略优化联合的方法;首先基于解析冗余关系(ARRs)把测试选择问题映射为一个特殊的0-1整数规划(IP)模型并用分支定界法求解之,得到最优测试;然后通过两步回溯改进的AO*算法确定最优测试顺序;在一个组合电路的应用表明算法优化了测试点数,减少了扩展节点数,降低了经典算法的复杂度。     

业务流程管理中的大规模整数规划问题求解

对从企业业务流程管理中抽象出来的大规模整数规划问题的计算机求解方法进行讨论。提出一种内存优化管理方法,能更高效地存储海量数据。同时对求解整数规划问题的经典算法——分枝定界算法进行研究,利用人工智能的搜索思想,给出分枝定界法的改进算法,使其能快速求解大规模整数规划问题。     

分支定界算法的分布并行化研究

介绍了一种专用于计算分支定界算法的机群计算平台,其中所使用的分布并行策略减少了分支定界算法计算时间复杂度,减小了问题的规模;可以把计算平台机群中的任何一台计算机上计算出的当前全局最佳本分值,实时地广播给所有其他并行的计算机,并作为它们新的最佳本分值,实现分支节点的快速并行淘汰;应用启发式算法修改了分支定界算法,提高了分支节点的淘汰效率。选用旅行商问题实例作为测试基准。计算表明,在保证求得最优解的前提下,该平台能很好地提高分支定界算法的效率。     

钢铁企业全流程物流优化问题的建模及分支——定价算法

研究了钢铁企业的全流程物流优化问题, 该问题在确保全流程各个工序机组产能和库存能力限制以及满足客户需求的前提下, 决策炼钢、连铸、热轧及冷轧工序间的物料流向和流量, 最小化物流成本、产能损失及库存费用. 为该问题建立了混合整数规划(Mixed integer programming, MIP)模型. 在问题求解中, 首先对MIP模型进行了Dantzig-Wolfe分解, 得到一个结构相对简单但列变量数目非常多的主问题和四个描述列向量空间的子问题. 然后, 从一个包含部分列变量的限制主问题出发, 通过子问题和主问题之间的迭代来获取主问题线性松弛的最优解. 最后, 将列生成同分支—定界相结合, 即分支—定价算法, 以获取原问题的整数最优解. 对某钢铁企业的实际生产数据扩展的随机算例进行仿真实验, 结果显示所提出的算法能够在合理计算时间内获得最优解或次优解.