大域的最適化アルゴリズムとその化学相平衡問題への応用

全局优化算法及其在化学相平衡问题中的应用

• 批准号: 01F00040
• 负责人: 久野 誉人
• 金额: $ 1.41万
• 依托单位: University of Tsukuba
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-01F00040/
• 关键词: 化学相平衡; 大域的最適化; 非線形計画; 整数計画; 分枝限定法; アルゴリズム

化学プロセスで解決の求められることの多い非線形0-1型混合整数計画問題は,0-1変数を固定すれば通常の凸計画問題に帰着するものの,正しい解を求めるためには,0-1変数の数の巾乗個もの凸計画問題の中から大域的に最適な解を与えるものを見つけ出さなければならない.このため,従来は発見的に精度保障のない近似解を求めるほか術がないとされてきたが,この多極値非凸最適化問題に対して厳密な最適解を生成する分枝カットアルゴリズムを構築した.対象となる問題を凸計画問題に連続緩和したときの最適解が,その実行可能領域における,ある1次関数の最小点に一致することを明かにした.これをもとに,緩和問題の最適解を離接切除平面によって効果的に除去する方法を考案した.離接切除平面は,0-1変数で離接が生じることを利用して各0-1変数の定めるアフィン空間に子問題を射影し,これを解くことによって生成する.しかし,射影された問題は非線形計画問題であり,アルゴリズムの各反復でこれを解くことは全体として効率的でない.そこで,この問題をさらに線形計画問題に緩和し,その双対問題を用いて切除平面が子問題に対して常に妥当となるように調整を行なった.同時に,残りの0-1変数の整数性も利用し,解を与えない領域をなるべく深く除去するように切除平面の強化を行なった.以上の方法で生成される離接切除平面は,必ずしも離接集合に対する凸包のファセットとはならない.しかし,予備実験では典型的な2つの化学設計問題に対して十分な効果のあることが確認できた.

The chemical solution of the nonlinear 0-1 type mixed integer program problem with fixed number 0-1 is to solve the convex program problem with fixed number 0 -1 and to solve the convex program problem with fixed number 0 -1. For this purpose, we propose a method for solving approximate solutions for precision assurance of multipole nonconvex optimization problems. The optimal solution to the convex problem is to solve the problem in the first order. The optimal solution of the mitigation problem is to consider the method of removing the discrete plane. The number 0 -1 of the disconnected cutting plane is 0 -1. The number 0-1 of the disconnected cutting plane is 0-1. The number 0 - 1 of the disconnected cutting plane is 0 - 1. The problem of projection is not linear planning problem. The problem of linear planning is mitigated by the problem of double pairs, and the problem of plane subproblems is corrected by the problem of double pairs. At the same time, the residual 0-1 integer number is used to solve the problem. The above method generates a disconnected cutting plane, which must be included in the disconnected set. In preparation for the typical chemical design problems, the results are confirmed.

项目成果

Zhn, Y., Kuno, T.: "A Disjunctive Cutting Plane Based Branch-and Cut Algorithm for 0-1 Mixed-Integer Non linear Problems"ISE Technical Report. 03・190. 1-30 (2003)

Zhn, Y., Kuno, T.：“针对 0-1 混合整数非线性问题的基于析取切割平面的分支和切割算法”ISE 技术报告 03・190 (2003)。

Zhn, Y., Kuno, T.: "Global Optimization of Nonconvex MILP by a Hybrid Branch-and-Bound and Revised General Benders Decomposition Approach"Ind. Eng. Chem. Res.. 42. 528-539 (2003)

Zhn, Y., Kuno, T.：“通过混合分支定界和修订的通用 Benders 分解方法对非凸 MILP 进行全局优化”Ind。