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

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的求解多目标离散优化问题的新算法。计划将该算法应用于现有方法难以解决的实际多目标问题。此外，还提出了一种基于熵的问题难易度估计方法。该技术拟应用于并行计算的问题划分方法中。

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.