組合せ最適化問題に対する半正定値計画緩和と線形計画緩和

组合优化问题的半定规划松弛和线性规划松弛

• 批准号: 12780337
• 负责人: 藤江 哲也
• 金额: $ 1.54万
• 依托单位: Kobe University of Commerce
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 2000
• 资助国家: 日本
• 起止时间: 2000 至 2001
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-12780337/
• 关键词: 組合せ最適化; 緩和問題; 半正定値計画; 線形計画; 一般化安定集合問題; 半正定値計画緩和

FIRフィルタ設計に関する最適化問題に対する緩和問題を扱った.この最適化問題は各変数のとりうる値が1または-1である二次計画問題({1,-1}二次計画問題)であり,目的関数が凸二次関数であるという特徴を持つ.過去の研究として半正定値計画緩和が提案されていたが,今回,半正定値計画緩和,二次錐計画緩和,線形計画緩和および三角不等式を加えることによる緩和の強化を定式化し,数値実験を行った.その結果,実験を行った範囲では,三角不等式を加えた線形計画緩和問題を解くことによって元問題の最適解が得られ,従来の半正定値計画緩和問題よりも優れていることが確認された.今後はこの結果の理論的根拠を与えることが課題となる.また,今回の研究を目的関数が凸の{1,-1}二次計画問題として定式化できる他の問題(数分割問題など)に適応し,緩和問題の有効性を示す必要がある.また,整数計画・組合せ最適化問題に対する分枝限定法・分枝カット法の実装の一環として,共同研究で行っているフレームワークを開発している.今年度は主に視覚化に関するプログラムに携わり,大規模な分枝限定木の表示部分を現在も開発中である.今後は分枝カット法のフレームワークの開発を中心に行い,整数計画問題を解くための実装,特にカットを生成するプログラムの開発を行う予定である.

FIR design related optimization problems and mitigation problems The optimization problem is a quadratic programming problem ({1,-1} quadratic programming problem) with the objective relation and convex quadratic relation. In the past, the study of semi-definite value plan mitigation was carried out. Now, the semi-definite value plan mitigation, quadratic cone plan mitigation, linear plan mitigation and triangular inequality mitigation are formulated. As a result, the optimal solution of the linear plan mitigation problem is obtained. The root of the theory of the future results of. In this paper, the objective of this study is to solve the convex {1,-1} quadratic programming problem and to formulate other problems (number division problems). In this paper, we discuss the problem of integer programming and combinatorial optimization. This year, the main visual aspects of the development of large-scale branching limit tree representation part now in development. In the future, the development of the branch method will be carried out in the center, and the integer project problem will be solved in the implementation, and the development of the branch method will be carried out in the predetermined time.