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

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

基本信息

批准号：
13780351
负责人：
繁野麻衣子
金额：
$ 1.15万
依托单位：
University of Tsukuba
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2001
资助国家：
日本
起止时间：
2001 至 2002
项目状态：
已结题

项目摘要

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

组合优化问题是使用几个数值数据具有特定组合结构的系统，并找到了最佳状态（解决方案）。在这项研究中，我们为逆优化问题开发了一种算法，这是一个纠正数据的问题，并且对于使数据更一般的问题进行了优化的问题，以便对给定的操作解决方案进行优化，以解决网络结构的问题。最小值最小切割问题的最小值类型的逆优化问题：纠正分支容量以使给定的削减的能力最小的能力的问题表明，它与最大平均削减问题有着深厚的联系，并且表明它可以通过将算法有效地解决，通过将算法应用于最大值的最大临界问题，以最小的速度成本为最小的成本问题。每个分支的增益/损失是最低成本。显示了与最小平均闭合问题的关系。此外，通过使用参数搜索对算法的详细分析，可以表明迭代次数保持在比以前已知的低。3。通用最大流量问题具有广义增益函数：在每个分支上具有增益/损失的广义网络中，增益/损失由线性函数给出。这种给出增益/损失数据的方法通常是凹功能，并且显示了当时最大流量问题的最佳条件和算法。