記号計算に基づいた並列最適化問題の研究

基于符号计算的并行优化问题研究

• 批准号: 10878044
• 负责人: 井田 哲雄
• 金额: $ 1.28万
• 依托单位: University of Tsukuba
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Exploratory Research
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 1999
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10878044/
• 关键词: 最適化問題; 線形整数計画問題; 論理式; 整数ラベル付けアルゴリズム; ILIN; Grobner基底; MGBA; 整数ラベル付け

本研究では,記号計算の成果を活用することにより,最適化問題の中でも重要な整数計画問題に対する新たな解法を与える.新しく得られた研究成果は次の通りである.1.論理式による問題記述法の提案高度に複雑な現実問題に対して整数計画法を応用する場合,問題をどのようにモデル化し記述するかが重要な問題となる.本研究では,一階述語論理の論理式により問題を記述すると,これを自動的に整数計画問題へと変換する理論的枠組を提案した.論理式を用いることで,従来知られている方法よりも問題のモデル化や解析が容易になった.論理式から整数計画問題への変換に関する研究成果の発表は,記号計算に関するシンポジウムIMS'99において行なった.また,研究論文は学術誌IEICEに掲載されることが決定している.(文献一覧を参照)2.ラベル付けアルゴリズムの実装シンプレックス行列により表現される連立1次方程式が整数解を持つかどうかの判定問題はNP完全であることが知られており,効率的な判定アルゴリズムを作るのは難しい.この問題の解法として,整数ラベル付け規則と行列の三角化に基づくYangのアルゴリズムが知られている.本研究では,このアルゴリズムを実現するシステムILINを作成し,大規模な(500変数の問題を含む)整数計画問題の解を求める実験を行なった.ラベル付けアルゴリズムの実装に関する研究成果は,学術誌IEICEに公表済みである.(文献一覧を参照)

In this paper, the results of symbolic calculation are used to solve the important integer planning problems in optimization. 1. The logical expression of the problem description method is highly complex, and the integer planning method is used in the case where the problem is described in detail. In this paper, we propose a new set of theories for describing the problems of first-order predicate logic and for solving the problems of integer programming automatically. The logical expression is easy to solve by using the method of solving the problem. The logical formula for integer planning problems and transformations is presented in the table of research results. The notation calculation is presented in the IMS'99 section. Research papers are published in academic journals. 2. The problem of determining the integer solution of a continuous first-order equation is NP complete. The solution of this problem is to solve the problem of integer class rules and triangulation of rows and columns. In this paper, we study how to solve the problem of integer planning on a large scale (500-digit). The research results related to the implementation of the project are presented in the academic journal IEICE. (Reference 1)

项目成果

Q.Li,Y.Guo,T.Ida: "Modelling Integer Programming with Logic: Language and Implementation"IEICE Trans.Fundamentals of Electronics,Communications and Computer Sciences. (印刷中). (2000)

Q.Li、Y.Guo、T.Ida：“用逻辑建模整数规划：语言和实现”IEICE Trans.Fundamentals of Electronics、Communications and Computer Sciences（出版中）。