论文部分内容阅读
混合整数非线性规划(MINLP)是数学规划中一类十分重要的问题。它是最为灵活,最为强大的建模优化框架之一。近年来研究者们采用MINLP在经济计划、工程设计、交通运输等各个领域内建立了一系列优化模型,产生了巨大的求解需求。其中的一部分问题对求解时间具有严格的约束。但是从目前来看,MINLP问题的求解效率还难以满足实际问题的需要。基于此,本文分别从串行和并行算法的角度出发,分别针对凸和非凸MINLP问题,提出了一系列提高MINLP计算效率的方法,同时也在此基础之上提出了一种分析MINLP最优解稳定性的方法。具体的研究内容总结如下。 1.针对凸MINLP的异构并行算法。传统的凸MINLP并行算法依赖于将一个问题分成多个相似的子问题,然后同时并行求解。理论上这种方法所能达到的最大加速比等于并行核心的数量。本文在分析了两个传统串行算法的优劣势的基础上,提出了一种异构并行算法。它将同一个问题分别交给两个不同的算法进行并行求解,通过两者之间的巧妙通讯,能够大大加速问题的求解。本文以多个算例分析了异构并行算法的优点,并说明了该方法理论上具备超线性加速的可能。 2.全局优化的改进分枝缩减算法。针对一般性MINLP问题的优化算法称为全局优化算法,它能够保障在有限时间内求解凸和非凸MINLP问题的全局最优解。通常这类问题的求解依赖于一系列松弛子问题的求解,其中就包括混合整数线性规划问题(MILP)。本文重点讨论了如何充分利用MILP的求解信息加速全局优化的求解。基于分枝缩减算法,本文围绕MILP的上界和下界,分别针对原算法中的分枝和缩减两个方面,提出了新的改进方法。其中对于分枝策略的改进能够大大加快一类非凸项仅涉及少数变量的问题的求解效率,而对于缩减的改进也使得大部分问题的求解速度得到了提升。最后本文通过多组实例分别验证了这两个方法的有效性。 3.全局优化的MILP策略及并行加速研究。MILP在全局优化求解器BARON的求解时间中占了相当大的比例,因此本文提出用并行MILP求解器的方法来减小这一环节的耗时,但是现有的MILP策略不适用于并行环境。同时对MILP的表现分析表明,现有的MILP策略在一些问题上的表现也不尽如人意。基于此本文提出了一个新型MILP触发策略,它能够克服现有方法的缺陷,并且能够根据不同问题、不同MILP求解器自发地调整求解频率。大量算例的测试表明新的MILP策略无论是在串行还是并行环境下求解效率相比现有策略都有明显进步。 4.MINLP最优解稳定性分析方法。在串行和并行求解算法的基础上,本文也进一步讨论了求解得到最优解后该怎样判断解的合理性和稳定性,从而指导合理决策。本文提出了一种在优化问题参数不确定的情况下绘制最优解分布图的方法,并以实际低温空气分离过程的调度问题为例说明了该分布图的绘制步骤,同时解释了该分布图的含义。通过空分调度的最优解分布图,在参数变化时,决策者能够直观地了解不同变量之间的稳定性,辅助他们进行最终的决策。 最后,本文总结了上述工作,并对进一步的研究进行了展望。