Improvement and application of target approach for solving nonlinear knapsack type optimization problem

求解非线性背包型优化问题的目标法改进及应用

• 批准号: 14580397
• 负责人: NAKAGAWA Yuji
• 金额: $ 2.05万
• 依托单位: Kansai University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2002
• 资助国家: 日本
• 起止时间: 2002 至 2005
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-14580397/
• 关键词: discrete optimization; multi-objective optimization; nonlinear knapsack problem; surrogate constraints method; financial engineering; exact method; near-optimization method; parallel computation; 組み合わせ最適化; ソフトウエア開発管理; 組み合ねせ最適化; 上界値計算法

1) Application of the improved surrogate constraint method to non-separable nonconvex portfolio optimization problemThe Improved Surrogate Constraint method (ISC) was developed, which cane solve exactly and efficiently large-scale multi-constraints separable discrete optimization problems. We apply the ISC to the index optimization problem that 50 brands are selected from 1440 brands of Tokyo Stock Exchange 1st section listed (TOPIX) and track the market index. This means that an extremely large-scale problem of a practical scale was able to be solved about the index fund problem. Moreover, it succeeded in making the index-plus-alpha portfolio. This result appeared in the Nikkan Kogyo Shimbun article Friday, November 18, 2005.2) Exact method for solving multi-constraints separable discrete optimization problemsIn order to apply the ISC method to a larger-scale problem, we tried to use average information (entropy) and to divide an original problem into small subproblems. The test problem of Chu and Beasley are used to show the effectiveness of the present method. The method is compared with business high speed software CPLEX V.9.0 by using 30 0-1 knapsack problems, which are well known as difficult problems. with 500 variables. The computational results show that the ISC using the Problem Partition is nine times as fast as CPLEX on the average and succeeds in economizing the memory.3) Multi-objective optimization and parallel computationWe developed a new solution algorithm based on the ISC for solving multi-objective discrete optimization problems. It is scheduled to apply the present algorithm to practical multi-objective problems that the existing methods are quite difficult to solve. Moreover, a estimation technique of the difficulty degree of the problem that used entropy was newly developed. This technology is scheduled to be applied to the problem partition method for the parallel computation.

1）将改进的替代约束方法应用于非分离的非convex投资组合优化问题，开发了改进的替代约束方法（ISC），甘蔗可以准确有效地求解可分开的离散优化问题。我们将ISC应用于指数优化问题，即从列出的东京证券交易所（Tokyo Stock Exchange）的1440个品牌中选择了50个品牌（TOPIX）并跟踪市场指数。这意味着，实用规模的一个非常大的问题可以解决指数基金问题。此外，它成功地制作了索引 - α级投资组合。该结果出现在2005年11月18日，星期五的尼康Kogyo Shimbun文章中，用于求解可分离的离散优化问题的确切方法，以将ISC方法应用于更大规模的问题，我们试图使用普通信息（熵）并将原始问题划分为小副标题。 Chu和Beasley的测试问题用于显示本方法的有效性。通过使用30 0-1 knapsack问题，该方法与业务高速软件CPLEX v.9.0进行了比较，这被称为困难问题。有500个变量。计算结果表明，使用问题分区的ISC平均是CPLEX的速度九倍，并成功地节省了内存。3）多目标优化和Parallel ComputationWe We开发了一种基于ISC的新解决方案算法，该算法基于解决多目标离散优化问题的ISC。它计划将当前算法应用于实用的多目标问题，而现有方法很难解决。此外，新开发了使用使用熵问题的难度程度的估计技术。该技术计划应用于并行计算的问题分区方法。

项目成果

The Reliability Optimization Problems by Means of Improved Surrogate Constraints Method

改进代理约束法的可靠性优化问题

• 发表时间: 2003
• 期刊: IEICE J86-A, 10
• 作者: S.Kimura;Y.Isada;Y.Nakagawa
• 通讯作者: Y.Nakagawa

A Problem Partition Method for Multidimensional Nonlinear Knapsack Problems Using Estimated Problem Difficulty

一种基于估计问题难度的多维非线性背包问题划分方法

• 发表时间: 2005
• 期刊: Working Paper [2005-02]. Faculty of Informatics, Kansai University
• 作者: Y.Nakagawa;Y.Isada;R.J.W.James
• 通讯作者: R.J.W.James

Enumerations Methods for Repeatedly Solving Multidimensional Knapsack Sub-Problems

反复求解多维背包子问题的枚举法

• 发表时间: 2005
• 期刊: Trans. IEICE Inf&Syst E88-D
• 作者: James;Nakagawa
• 通讯作者: Nakagawa

An improved surrogate constraints method for separable nonlinear integer programming

可分离非线性整数规划的改进代理约束方法

• 发表时间: 2003
• 期刊: Journal of the Operations Research Society of Japan 46
• 作者: Nakagawa

代理制約法における代理乗数決定のための改良Dyerアルゴリズムの特性評価

替代约束法中确定替代乘数的改进Dyer算法的特性评估

• 发表时间: 2004
• 期刊: 日本経営工学会論文誌 55
• 作者: 木村;太田垣;仲川
• 通讯作者: 仲川