@article{oai:ipsj.ixsq.nii.ac.jp:00017187,
 author = {田村, 慶一 and 岩木, 稔 and 高木, 允 and 北上, 始 and Keiichi, Tamura and Minoru, Iwaki and Makoto, Takaki and Hajime, Kitakami},
 issue = {SIG17(TOM13)},
 journal = {情報処理学会論文誌数理モデル化と応用（TOM）},
 month = {Dec},
 note = {線形計画問題の一部の変数に対して整数制約を加えた問題を混合整数計画問題という．本論文では，分枝限定法と単体法を用いた混合整数計画問題解法のPC クラスタにおける並列化手法を提案する．並列化には典型的なマスタワーカモデルを使用する．課題となったのが負荷の偏りと総探索ノード数の増加である．負荷の偏りに関してはタスク奪い取りによる動的負荷分散手法であるマスタ・タスク・ステイル法を用い，総探索ノード数の増加に関しては暫定解同期を行い，課題を解決する．提案する並列化手法を実際に実装し，PC クラスタ上で数値実験を行った．数値実験により，提案する並列化手法で2 つの課題を解決できていることを確認できた．, A problem in which some variables of a linear programming problem can take only integer values and some variables can take fractional values is called a mixed-integer programming problem. The mixed-integer programming problem is solved using both the simplex method branch-and-bound algorithm. This paper proposes a parallelism of the mixed-integer programming problem on a PC cluster. The parallelism of the mixed-integer programming problem uses a task-divided-based master-worker model. There are two problems; inefficient loadbalancing and increasing the total number of search nodes. To overcome the first problem, a task-steal-based dynamic load balancing technique Master-Task-Steal method is used for the dynamic load balancing of master-worker model. To solve the second problem, we propose synchronous techniques of incumbent. We implemented parallel mixed-integer programming problem on an actual PC clusters. The experimental results show that the two problems are not occured.},
 pages = {56--69},
 title = {PCクラスタにおける混合整数計画問題の並列処理とその性能評価},
 volume = {46},
 year = {2005}
}