Developments of Advanced Optimization Systems Unitying Discrete and Continuous Approaches Associate

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

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.