データの精度を考慮した組合せ最適化問題に対する問題構造とアルゴリズムの研究

考虑数据精度的组合优化问题的问题结构和算法研究

• 批准号: 13780351
• 负责人: 繁野 麻衣子
• 金额: $ 1.15万
• 依托单位: University of Tsukuba
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13780351/
• 关键词: ネットワーク流問題; 逆最適化問題; 多項式時間アルゴリズム; 一般化ネットワーク

組合せ最適化問題は,いくつかの数値データを用いてある組合せ構造をもつシステムを表し,最適な状態(解)を求める.本研究では,主にネットワーク構造をもつ問題を対象に,与えられた実行可能な解を最適にするように,逆にデータを修正する問題である逆最適化問題や,データの与え方をより一般的にした問題に対するアルゴリズムの開発を行った.1.最小カット問題に対するミニマックス型逆最適化問題:与えられたカットが最小容量をもつように,枝容量を修正する問題.最大平均カット問題と深い関わりがあることを示し,最大平均カット問題に対するアルゴリズムを適用することで効率的に解けることを示した.2.一般化最小費用流問題に対するミニマックス型逆最適化問題:各枝に利得/損失のある一般化ネットワーク上の実行可能流が最小費用となるように枝費用を修正する問題.最小平均閉路問題との関係を示した.さらに,パラメトリックサーチによるアルゴリズムを詳しく解析することで,繰り返し回数がこれまで知られている回数よりも少なく押さえられることを示した.3.利得関数を一般化した一般化最大流問題:各枝に利得/損失めある一般化ネットワークでは,その利得/損失は線形関数で与えられていた.この利得/損失のデータの与え方をより一般的に凹関数とし,そのときの最大流問題に対する最適性条件とアルゴリズムを示した.

Combinatorial optimization problem is to construct a combinatorial optimization problem and find the optimal state (solution). In this paper, we study the inverse optimization problem of the main structure optimization problem, and the inverse optimization problem of the branch capacity correction problem. 2. Generalized minimum cost flow problem: gain/loss problem of each branch. The minimum average closed circuit problem is shown. 3. Generalization of the gain relationship. Generalization of the maximum flow problem. Generalization of the gain/loss relationship. Generalization of the gain/loss relationship. The optimal conditions for the maximum flow problem are shown below.

项目成果

Maiko SHIGENO: "Minimum Maximal Flow Problem-An Optimization over the efficient sets-"Journal of Global Optimization. (掲載予定).

Maiko SHIGENO：“最小最大流问题 - 有效集上的优化 -”全局优化杂志（待出版）。

Maiko SHIGENO: "Maximum Network Flows with Concave Gains"Discussion Paper, Institute of Policy and Planning Sciences, Univ. of Tsukuba. 1027. (2003)

Maiko SHIGENO：“Maximum Network Flows with Concave Gains”讨论论文，政策与规划科学研究所，大学。

Jun OHTA: "A Note on Minimax Inverse Generalized Minimum Cost Flow Problems"Discussion Paper, Institute of Policy and Planning Science, Univ. of Tsukuba. 976. (2002)

Jun OHTA：“A Note on Minimax Inverse Generalized Minimum Cost Flow Problems”讨论论文，政策与规划科学研究所，大学。

Maiko SHIGENO: "Minimax Inverse Problems of Minimum Cuts"Networks. 39. 7-14 (2002)

Maiko SHIGENO：“最小割的极小极大逆问题”网络。

Maiko SHIGENO: "Minimax Inverse Problem of Minimum Cuts"Networks. 39. 7-14 (2002)

Maiko SHIGENO：“最小割的极小极大逆问题”网络。