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.