半正定値計画の組み合わせ最適化問題への応用

半定规划在组合优化问题中的应用

• 批准号: 08650459
• 负责人: 小島 政和
• 金额: $ 1.41万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 1996
• 资助国家: 日本
• 起止时间: 1996 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-08650459/
• 关键词: 半正定値計画問題; 組み合わせ最適化問題; 0-1整数計画問題; 主双対内点法

本年度に計画した研究目標は以下の通りであった.1.一般的な半正定値計画問題に対して開発した主双対内点法のプログラム計算効率を高める.2.0-1整数計画問題の数値解法の主要部分を構成する予定の半正定値計による緩和について,より効果のある緩和について模索する.3.半正定値計画による緩和と既存の手法である切除平面法または分枝限定組み合わせについて研究する.研究目標1に関しては,組合せ最適化問題から生ずる過疎で大規模な半定値計画問題を高速に解けるように,プログラムの改訂を行い,そのさまざまな組合せ最適化問題から生ずる半正定値計画問題に適用しその有効性を検証した.また,この段階で目標2に関しての計算実験もあわせて行った.プログラムをインターネットを通して公開した.目標1に関しては最初に計画した以上の成果をあげた.しかしながら,目標1の達成に時間がかかり,目標3に関する研究はあまり進まなかった.この主たる理由は目標2および3に関する研究の中途で,より大規模な半正定値計画問題を解くためのソフトウエアが必要であることが判明し,主双対内点法のより大幅な改定が必要になったためである.

This year's program aims at the following general problems: 1. general semi-definite value planning problems; 2. 0 -1 numerical value solutions for integer planning problems; 3. 3. Semi-definite value planning, mitigation and existing methods, cutting plane method, branching limit group and combination Objective 1: To prove the applicability of combinatorial optimization problem to large scale semidefinite planning problem. The calculation of this stage is based on the calculation of the stage 2. The most important thing is to open up the market to the public. Goal 1: The original plan. Goal 1 is achieved at the same time as Goal 3. The main reason for this is that in the middle of the study, the problem of large scale semi-definite planning is solved, and it is necessary to determine the main two-pair interior point method.

项目成果

小島政和: "Basic Lemmas in Polynomial-Teme Infeasible-Interior-Point Methods for Linear Programs" Annals of Operations Reseearch. 62. 1-28 (1996)

Masakazu Kojima：“线性规划多项式不可行内点方法中的基本引理”运筹学年鉴 62. 1-28 (1996)。

藤江哲也、小島政和: "Semidefinite Programming Relaxation for Nonconvex Quadratic Programms" Jounal of Global Optimization. (掲載予定).

Tetsuya Fujie、Masakazu Kojima：“非凸二次规划的半定规划松弛”全局优化杂志（待出版）。

小島政和: "Interior-Point Methods for the Monotone Linear Complementarity Problems in Symmetric Matrices" SIAM J.Optimization. (掲載予定).

Masakazu Kojima：“对称矩阵中单调线性互补问题的内点方法”SIAM J.Optimization（即将出版）。