Global optimization of mixed-integer nonlinear programs: A theoretical and computational study
Global optimization of mixed-integer nonlinear programs: A theoretical and computational study
复制标题
DOI：
10.1007/s10107-003-0467-6
复制
发表时间：
2004-04
影响因子：
2.7
通讯作者：
Mohit Tawarmalani;N. Sahinidis
中科院分区：
文献类型：
--
作者：
Mohit Tawarmalani;N. Sahinidis
这项工作解决了一个有效的解决方案，以获得连续，整数和混合整数非线性规划的全局最优解的策略的发展。为此，我们开发了新的放松计划，范围缩小测试，分支策略，我们纳入到原型分支定界算法。在本文的理论/算法部分，我们开始通过开发新的策略来构建混合整数非线性规划的线性松弛，并证明这些松弛享受二次收敛性质。然后，我们使用拉格朗日/线性规划对偶发展一个统一的理论域减少战略的后果，我们得到许多范围减少目前使用的非线性规划和整数线性规划的战略。这一理论导致了新的范围缩减方案，包括通过在分支定界树中跨兄弟节点中继数据来改进初始分支决策的学习启发式。最后，我们将这些放松和减少策略的分支定界算法，采用分支策略，保证有限的某些类别的连续全局优化问题。在本文的计算部分，我们描述了我们的实现讨论，在适当的情况下，使用合适的数据结构和相关的算法。我们目前的计算经验与基准可分离凹二次规划，分数0-1计划，并从应用程序中的化学过程，工程设计，即时制造和分子设计的合成混合整数非线性规划。
This work addresses the development of an efficient solution strategy for obtaining global optima of continuous, integer, and mixed-integer nonlinear programs. Towards this end, we develop novel relaxation schemes, range reduction tests, and branching strategies which we incorporate into the prototypical branch-and-bound algorithm. In the theoretical/algorithmic part of the paper, we begin by developing novel strategies for constructing linear relaxations of mixed-integer nonlinear programs and prove that these relaxations enjoy quadratic convergence properties. We then use Lagrangian/linear programming duality to develop a unifying theory of domain reduction strategies as a consequence of which we derive many range reduction strategies currently used in nonlinear programming and integer linear programming. This theory leads to new range reduction schemes, including a learning heuristic that improves initial branching decisions by relaying data across siblings in a branch-and-bound tree. Finally, we incorporate these relaxation and reduction strategies in a branch-and-bound algorithm that incorporates branching strategies that guarantee finiteness for certain classes of continuous global optimization problems. In the computational part of the paper, we describe our implementation discussing, wherever appropriate, the use of suitable data structures and associated algorithms. We present computational experience with benchmark separable concave quadratic programs, fractional 0–1 programs, and mixed-integer nonlinear programs from applications in synthesis of chemical processes, engineering design, just-in-time manufacturing, and molecular design.