Developments of Advanced Optimization Systems Unitying Discrete and Continuous Approaches Associate

结合离散和连续方法的高级优化系统的开发

基本信息

批准号：
07555615
负责人：
IMAI Hiroshi
金额：
$ 1.22万
依托单位：
The University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (B)
财政年份：
1995
资助国家：
日本
起止时间：
1995 至 1996
项目状态：
已结题

项目摘要

Optimization methods by computers have a great impact upon various fields in science and technology due to its wide scope of applications. In this research project, was have aimed at unifying existing results for system analysis obtained by each of project members on interiorpoint methods for linear programming, computational-geometric algorithms, matroid theory, Boolean function theory, etc., and produce new theoretical results and devrlop prototype optimization systems via this unifying work.Through this project, from the viewpoint of continuous optimization, we have extended the framework of linear programming to that of semidefinite programming, and, from the viewpoint of discrete optimization, theory of discrete convex analysis has been developed. By this theory of discrete convex analysis, connection with continuous methods and discrete methods can be established, with extending matroids and submodular systems on which the discrete convexity theory is based. Randomization is also applied through this connection between continuous and discrete approaches, and, by applying the randomized rounsing technique using the semidefinite programming to the satisfiability problem, approximate algorithms with better porformance ratio have been obtained. Furthermore, based on polyhedral structures having both continuous and combinatorial properties, the branch-and-cut technique is applied to the famous minimum-length triagulation problem in computational geometry. Finally, we developed a prototype system handling a family of sets by using the so-called binary decision diagram (or, BDD) as a promising approach from discrete Boolean function theory, and applied it to various problems, including network reliability computation which have continuous aspect, and other invariants in graphs, knots, and statistical physics. The system is made public for wide use.

计算机优化方法因其广泛的应用范围而对科学技术的各个领域产生了巨大的影响。在这个研究项目中，旨在统一每个项目成员在线性规划内点方法、计算几何算法、拟阵理论、布尔函数理论等方面获得的系统分析的现有结果，并产生新的理论结果和开发通过这项统一的工作，原型优化系统。通过这个项目，从连续优化的角度，我们将线性规划的框架扩展到半定规划的框架，并且从离散优化的角度，发展了离散凸分析的理论。通过离散凸分析理论，可以建立连续方法和离散方法的联系，以及离散凸性理论所基于的扩展拟阵和子模系统。随机化也通过连续方法和离散方法之间的这种联系来应用，并且通过将使用半定规划的随机循环技术应用于可满足性问题，获得了具有更好性能比的近似算法。此外，基于具有连续性和组合性的多面体结构，将分支切割技术应用于计算几何中著名的最小长度三角剖分问题。最后，我们开发了一个处理一系列集合的原型系统，使用所谓的二元决策图（或 BDD）作为离散布尔函数理论的一种有前途的方法，并将其应用于各种问题，包括具有连续性的网络可靠性计算方面，以及图、结和统计物理中的其他不变量。该系统已公开供广泛使用。