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)改进的代理约束方法在不可分非凸投资组合优化问题中的应用提出了改进的代理约束方法（ISC），该方法能够精确、高效地求解大规模多约束可分离散优化问题。我们将ISC应用于指数优化问题，从东京证券交易所（TOPIX）的1440个品牌中选择50个品牌，并跟踪市场指数。这意味着指数基金问题能够解决一个具有实际规模的极大规模问题。此外，它还成功地建立了指数加阿尔法的投资组合。这一结果发表在2005年11月18日（星期五）的Nikkan Kogyo Shimbun文章中（5.2）求解多约束可分离离散优化问题的精确方法为了将ISC方法应用于更大规模的问题，我们尝试使用平均信息（熵）并将原始问题划分为小的子问题。用Chu和Beasley的测试问题验证了该方法的有效性。以30个众所周知的难解问题0-1背包问题与商业高速软件CPLEX V.9.0进行比较。有500个变量。计算结果表明，使用问题分区的ISC平均速度是CPLEX的9倍，并且成功地节省了内存。3)多目标优化与并行计算我们提出了一种基于ISC的求解多目标离散优化问题的新算法。计划将该算法应用于现有方法难以解决的实际多目标问题。此外，还提出了一种基于熵的问题难易度估计方法。该技术拟应用于并行计算的问题划分方法中。

项目成果

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

The Reliability Optimization Problems by Means of Improved Surrogate Constraints Method

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

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

Enumerations Methods for Repeatedly Solving Multidimensional Knapsack Sub-Problems

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

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

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

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

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

An improved surrogate constraints method for separable nonlinear integer programming

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

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