The trial production of generalized solver for optimization problems on HTC environments

HTC环境下优化问题广义求解器的试制

• 批准号: 13680511
• 负责人: SHINANO Yuji
• 金额: $ 1.73万
• 依托单位: Tokyo University of Agriculture and Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13680511/
• 关键词: Combinatorial optimization; Branch-and-bound algorithms; HTC; PC cluster

First of all, based on "The research purpose and research plan" indicated in the grant application, I show the targets at the time of the application. The targets within the research period for two years are as follows.(1) The trial production of a system which implemented general parallel branch-and-bound algorithms on the HTC environments where 1000 or more PCs and workstations are connected with Internet or LAN (In its design, it is afford to operate general-purpose meta-heuristic solver in parallel).(2) Having a clear grasp of the problems when building a generalized solver on HTC environments(3) Having a grasp of limitations for using the generalized solver in the HTC environmentsWe have been developed PUBB2 (Parallelization Utility for Branch-and-Bound algorithms version 2) in this research period. About (1) and (2), it was attained through development of PUBB2 except for the point that execution by 1000 or more sets of the HTC environment was not actually performed. In PUBB2, im … More plementing a few functions which are forced to override in its framework, enable to build a new layer of a new execution environment. Moreover, an algorithm of load balancing for parallel and distribution execution can be implemented 〓〓exibly by developing new specialized classes which are derived from ProblemManager class in PUBB2. Although the code for a layer of 〓RID environment was underdeveloped, using the software tool we built, a new framework itself can be developed flexibly and easily.About (3) of the above target, we tried to parallelize ILOG CPLEX MIP Optimizer which is commercial based solver for a mixed integer problem using PUBB2 framework. The ILOG CPLEX MIP Optimizer is regarded as one of the fastest and the most robust MIP Optimizer in the world. It have been reflected not only the theoretically new research results, but also it is the sophisticated program with refined memory management etc. Therefore, even the parallel system for GRID etc. does not usually have the same performance as a CPLEX run on a single computer. The parallelization utility should parallelize the latest products. Then, as one of the evaluation of our prototype system, we verified whether if our prototype of our general framework can be parallelize the MIP Optimizer efficiently or not.The main product of this research is having developed the prototype system. Therefore, Reference Manual automatically generated from developed program source code is included in the final report. Since the research period was spent on development, although there was no refereed paper published, the results are summarized in two papers that are included in the final report. One of the papers has been accepted. Less

首先，根据资助申请中注明的“研究目的和研究计划”，我展示了申请时的目标。两年研究期间的目标如下：（1）在1000台或更多PC和工作站与互联网或局域网连接的HTC环境上试制一个实现通用并行分支定界算法的系统（在其设计中，能够并行运行通用元启发式求解器）。（2）在HTC上构建通用求解器时清楚地掌握问题 (3) 掌握在 HTC 环境中使用广义求解器的局限性 我们在本研究期间开发了 PUBB2（分支定界算法并行化实用程序版本 2）。关于(1)和(2)，除了实​​际未执行1000套或更多HTC环境的这一点之外，它是通过PUBB2的开发而实现的。在PUBB2中，我实现了一些在其框架中强制覆盖的功能，从而能够构建新的执行环境的新层。此外，通过开发从PUBB2中的ProblemManager类派生的新的专用类，可以灵活地实现并行和分布执行的负载平衡算法。虽然〓RID环境层的代码尚未开发，但使用我们构建的软件工具，可以灵活、轻松地开发新的框架本身。关于上述目标的（3），我们尝试使用PUBB2框架对ILOG CPLEX MIP Optimizer进行并行化，该求解器是基于商业的混合整数问题求解器。 ILOG CPLEX MIP 优化器被认为是世界上最快、最强大的 MIP 优化器之一。它不仅体现了理论上新的研究成果，而且是具有精细化内存管理等的复杂程序。因此，即使是GRID等并行系统，通常也不具有与在单台计算机上运行的CPLEX相同的性能。并行化实用程序应该并行化最新的产品。然后，作为对我们的原型系统的评估之一，我们验证了我们的通用框架的原型是否可以有效地并行化MIP优化器。本研究的主要成果是开发了原型系统。因此，从开发的程序源代码自动生成的参考手册包含在最终报告中。由于研究期间主要用于开发，虽然没有发表任何参考论文，但结果总结在两篇论文中，并包含在最终报告中。其中一篇论文已被接受。较少的

项目成果

Yuji Shinano, Tetsuya Fuje, Yuusuke Kounoike: "Effectiveness of Parallelizing the ILOG-CPLEX Mixed Integer Optimizer in the PUBB2 Framework"Lecture Notes in Computer Science. 2790, to appear.. (2003)

Yuji Shinano、Tetsuya Fuje、Yusuke Kounoike：“PUBB2 框架中并行化 ILOG-CPLEX 混合整数优化器的有效性”计算机科学讲义。

Yuji Shinano, Tetsuya Fuje, Yuusuke Kounoike: "Parallelizing the ILOG-CPLEX Mixed Integer Optimizer in the PUBB2 Framework"The Institute of Statistical Mathematics Cooperative Research Report, Optimization - Modeling and Algorithms. 17, to appear..

Yuji Shinano、Tetsuya Fuje、Yusuke Kounoike：“在 PUBB2 框架中并行化 ILOG-CPLEX 混合整数优化器”统计数学研究所合作研究报告，优化 - 建模和算法。

Yuusuke Kounoike, Yuji Shinano, Tetsuya Fuje: "Prototyping of the LP-based MIP Solver for Evaluating the Effect of New Solving Techniques"The Institute of Statistical Mathematics Cooperative Research Report, Optimization - Modeling and Algorithms. 17, to

Yuusuke Kounoike、Yuji Shinano、Tetsuya Fuje：“基于 LP 的 MIP 求解器的原型设计，用于评估新求解技术的效果”​​统计数学研究所合作研究报告，优化 - 建模和算法。