連続系の数理計画法アルゴリズム
一次元連続ビンパッキング問題に対する厳密解法 (21世紀の数理計画 : アルゴリズムとモデリング)
... 一次元連続ビンパッキング問題に対する厳密解法 (An Exact Method for the One-dimensional Contiguous Bin Packing Problem) 京都大学・情報学研究科 荒堀洋平 (Yohei Arahori)* Graduate School of Informatics, Kyoto University ...
15
密輸量決定戦略のある密輸取締ゲーム (21世紀の数理計画 : 最適化モデルとアルゴリズム)
... et al[4] がある. そこでは , 複数回実施可能な不法行為実施中のパトロールは必ずしも完全ではなく,「摘 発」 ,「不法行為成功」,「そのいずれでもない」の 3 つの結果が確率的に生じ , 取締機関 , 密輸者の両プレイ ヤーのどちらの任務達成確率も考慮されたモデルとなっている. Hohzaki のモデルでは , 任務達成確率が ...
11
半正定値計画問題に対するソフトウェア開発で用いられる新技術について (21世紀の数理計画 : アルゴリズムとモデリング)
... 最適化などの様々の分野において, 想定する問題の規模 . 適用する手法, 実問題への適用 可能性などの最適化問題に対するパラダイムに大きな変化が生じるようになった [8]. た だし計算量の理論から考察すると $\mathcal{N}\mathcal{P}$ -困難な問題は問題の大きさが増加するにつれて, ...
12
重心のバランスを考慮した円と長方形の詰込み問題に対する混合整数DC計画法に基づいた手法 (数理最適化の発展 : モデル化とアルゴリズム)
... “A framework of discrete DC pro‐ gramming by discrete convex analysis.. Mathematical Programming 152.1‐2.[r] ...
12
印刷工程における段取り回数最小のモデル化 (21世紀の数理計画 : 最適化モデルとアルゴリズム)
... 式 (15) によって優先度が与えられたオペレーションを $O_{h_{i}j}\in PR^{a}$ とし , 優先度が与えられていな いオペレーション $O_{h_{i}j}\in PR^{b}$ として区別する. ここで, $PR^{a}$ と $PR^{b}$ は処理ごとに更新される. オペレーション $\forall O_{h_{\dot{t}}j}\in P_{i}^{a},\forall O_{h_{i}j}\in ...
10
様々な多重代入法アルゴリズムの比較～大規模経済系データを用いた分析～
... Handling Nonignorable Nonresponse Using Generalized Calibration with Latent Variables (Ranalli, Matei, and Neri, 2013) 概要：本報告では、対象変数の有限母集団合計値や平均値の推定が関心事である場合にお ...
44
Robust minimax receding horizon 制御問題の一解法 (21世紀の数理計画 : 最適化モデルとアルゴリズム)
... In the standard RHC formulation, the current control action is obtained by solving a finite or infinite horizon quadratic cost prob-.. lem at every sample time using the current state of[r] ...
10
線形計画問題に対する単体法の計算量と強多項式アルゴリズム (最適化アルゴリズムの進展 : 理論・応用・実装)
... た場合の計算量を求めた。 その結果、 線形計画問題の係数行列 $A$ が全ユニモジュラなら ば、 そのアルゴリズムが強多項式となることを示した。 なお、 単体法で各問題が確実に解 けることを保証するためには、 解くべき補助問題がすべて非退化であることを仮定する必 要がある。 理論的に少し強い条件であるが、 実際に単体法で問題を解くときに巡回に陥る ...
10
絶対値計画問題に対する主双対法と逐次線形化アルゴリズム (21世紀の数理計画 : アルゴリズムとモデリング)
... あたりの平均 , $(lif$ は作成した問題の既知の最適解と得られた解との差のベクトルの無限 大ノルムが $10^{-5}$ よりも大きかった問題数 , gap は得られた解において双対ギャップが $10^{-3}$ より大きかった問題数 , pf と df は得られた解がそれぞれ主問題と双対問題の実行可能解 でなかった問題数である . ...
14
発展方程式の平衡点の数値検証の力学系的アプローチ (科学技術計算アルゴリズムの数理的基盤と展開)
... 線型作用素のスペクトルの情報を併用した定常解の局所一意性，双曲性検証定理を述べる． 5 節では，実際に 数値検証すべき条件を考察し，不動点の存在とそれを含む不変集合の Conley 型指数を計算できるような集 合の構成法を述べる．数値検証に用いる数値解法としては，有限要素法を用いる．それにより，様々な境界 ...
16
組合せの効率的な生成法 (計算機科学とアルゴリズムの数理的基礎とその応用)
... Abstract: An unranking algorithm of a finite set $S$ is an algorithm such that, given a number in.. $\{0,1, \ldots, |S|-1\}$ , it returns an element of $S$ which is associated with the n[r] ...
8
最急上昇法による尾根抽出 (計算機科学とアルゴリズムの数理的基礎とその応用)
... 個のセルから一番大きな標高値をもつも抽出地形図までの作成プロセスを示す．その作成プ のを選択し，線を引く方法である．さらに，この方ロセスを用いて，日本と韓国の尾根抽出地形図を作 法がシンプルかつ日本全土のような広大な範囲に適成する．最後に， 5 ...
4
パラメトリックな劣モジュラ交わり問題の構造理論 (21世紀の数理計画 : 最適化モデルとアルゴリズム)
... The parametric submodular intersection problem and related problems have appeared. in the literature as follows[r] ...
11
非負行列分解による画像の構成部品抽出 (21世紀の数理計画 : 最適化モデルとアルゴリズム)
... $P_{1}(F, W)\Vert s.t\min_{u_{sk}}$ $u_{sk} \geq\sum_{s\in \mathcal{M}}\sum_{t\in \mathcal{N}}|f_{st}-$ $\sum_{k\in R,0}u_{\epsilon k}w_{kt1}$ $\forall s\in \mathcal{M},\forall k\in \mathcal{R}$ Pl $(F, W)$ は, 変数 ...
9
自動残差修正機能付き GBiCGSTAB$(s,L)$法 (科学技術計算アルゴリズムの数理的基盤と展開)
... AC-GBiCGSTAB 法と DC-GBiCGSTAB 法の収束履歴は，似ているものの微妙に異なる ことが分かる． 最後に， AC-GBiCGSTAB 法， DC-GBiCGSTAB 法の全般的有効性を見るために，表 2 に， 30 個の行列に対して， GBiCGSTAB 法， AC-GBiCGSTAB 法， ...
11
多項式記憶量による非線形大域的最適化 (21世紀の数理計画 : 最適化モデルとアルゴリズム)
... れるので , このことを求解に利用することができる. 特に, 目的関数 $f$ が複数の 1 変数関数 の和に分離可能な場合, 現実的な計算時間で最適解を求めることが可能である . 本研究では , このような最小化問題を問題規模の多項式の記憶量で解くアルゴリズムを提案する . 2 節で既 ...
9
波動問題などに対する代用電荷法の数理的性質 (数値解析と数値計算アルゴリズムの最近の展開)
... となる．一方，数値実験結果は下記のとおりである．波数 $k$ が $k\rho=1$ および 10 で与えら れる場合について，代用電荷法の誤差 $\epsilon_{N}$ をいくつかの $q$ の値に対して計算し，その結果 を図 5 に示した．図より，誤差 $\epsilon_{N}$ は $N$ に対し指数関数的に減衰することが分かる．そこ で，誤差 ...
14
自動残差修正機能付き GBiCGSTAB$(s,L)$法 (科学技術計算アルゴリズムの数理的基盤と展開)
... 彼等は，まず， $\triangle r_{k}$ と $A\triangle x_{k}$ から計算される量 $\frac{\Vert\triangle r_{k}+A\triangle x_{k}\Vert}{\Vert b\Vert}$ (櫻井等は inconsistency と読んでいる ) が偽収束の指標となることに注目した．しかし，この量の計算は重いので， inconsistency ...
11
線形二次錐計画問題に対する半無限計画変換を用いた単体法的アプローチ (21世紀の数理計画 : アルゴリズムとモデリング)
... ただし, $\delta>0$ を与えられた正の定数であり, $ll^{n}\in \mathbb{R}^{r?}$ は各成分が $(-1.1)$ の一様乱数となるよ うに生成した乱数ベクトルである . このように $b^{k}$ を順々に変化させて生成される問題列に対し て, SDPT3 を用いて解を求めた場合と DSPE 法を用いて解を求めた場合で計算時間を比較す る . ここで , ...
14
配置コストをもつ長方形詰込み問題に対する局所探索法の高速化 (最適化の数理とアルゴリズム)
... と計算できる . ただし , $r_{i}= \min_{j\in J_{i}^{\mathrm{b}}\backslash \{i\}j}x(\pi)$ である. ここで求めた各長方形の $x$ 座標は, 上述の $p_{\max}(\pi)$ の最小値を実現し , 各長方形のコスト関数を局所的に最小化している . この計算にかかる時間は , ...
9