{"updated":"2025-01-22T23:28:31.191556+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00017187","sets":["934:989:1002:1003"]},"path":["1003"],"owner":"1","recid":"17187","title":["PCクラスタにおける混合整数計画問題の並列処理とその性能評価"],"pubdate":{"attribute_name":"公開日","attribute_value":"2005-12-15"},"_buckets":{"deposit":"ce92abfa-0214-4ded-ad59-6dc5bf65aeaf"},"_deposit":{"id":"17187","pid":{"type":"depid","value":"17187","revision_id":0},"owners":[1],"status":"published","created_by":1},"item_title":"PCクラスタにおける混合整数計画問題の並列処理とその性能評価","author_link":["0","0"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"PCクラスタにおける混合整数計画問題の並列処理とその性能評価"},{"subitem_title":"Parallel Processing of Mixed Integer Programming Problem on PC Cluster and Its Performance Evaluation","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"オリジナル論文","subitem_subject_scheme":"Other"}]},"item_type_id":"3","publish_date":"2005-12-15","item_3_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"広島市立大学情報科学部"},{"subitem_text_value":"広島市立大学情報科学部 現在，NEC フィールディング株式会社"},{"subitem_text_value":"広島市立大学大学院情報科学研究科"},{"subitem_text_value":"広島市立大学情報科学部"}]},"item_3_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Faculty of Information Sciences Hiroshima City University","subitem_text_language":"en"},{"subitem_text_value":"Faculty of Information Sciences Hiroshima City University,Presently with NEC Fielding, Ltd.","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Information Sciences Hiroshima City University","subitem_text_language":"en"},{"subitem_text_value":"Faculty of Information Sciences Hiroshima City University","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/17187/files/IPSJ-TOM4617007.pdf"},"date":[{"dateType":"Available","dateValue":"2007-12-15"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-TOM4617007.pdf","filesize":[{"value":"864.1 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"17"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"89193765-a2a3-44ed-a0ea-bcd0d883898a","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2005 by the Information Processing Society of Japan"}]},"item_3_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"田村, 慶一"},{"creatorName":"岩木, 稔"},{"creatorName":"高木, 允"},{"creatorName":"北上, 始"}],"nameIdentifiers":[{}]}]},"item_3_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Keiichi, Tamura","creatorNameLang":"en"},{"creatorName":"Minoru, Iwaki","creatorNameLang":"en"},{"creatorName":"Makoto, Takaki","creatorNameLang":"en"},{"creatorName":"Hajime, Kitakami","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_3_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AA11464803","subitem_source_identifier_type":"NCID"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_6501","resourcetype":"journal article"}]},"item_3_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"1882-7780","subitem_source_identifier_type":"ISSN"}]},"item_3_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"線形計画問題の一部の変数に対して整数制約を加えた問題を混合整数計画問題という．本論文では，分枝限定法と単体法を用いた混合整数計画問題解法のPC クラスタにおける並列化手法を提案する．並列化には典型的なマスタワーカモデルを使用する．課題となったのが負荷の偏りと総探索ノード数の増加である．負荷の偏りに関してはタスク奪い取りによる動的負荷分散手法であるマスタ・タスク・ステイル法を用い，総探索ノード数の増加に関しては暫定解同期を行い，課題を解決する．提案する並列化手法を実際に実装し，PC クラスタ上で数値実験を行った．数値実験により，提案する並列化手法で2 つの課題を解決できていることを確認できた．","subitem_description_type":"Other"}]},"item_3_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"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.","subitem_description_type":"Other"}]},"item_3_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"69","bibliographic_titles":[{"bibliographic_title":"情報処理学会論文誌数理モデル化と応用（TOM）"}],"bibliographicPageStart":"56","bibliographicIssueDates":{"bibliographicIssueDate":"2005-12-15","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"SIG17(TOM13)","bibliographicVolumeNumber":"46"}]},"relation_version_is_last":true,"weko_creator_id":"1"},"created":"2025-01-18T22:50:15.102480+00:00","id":17187,"links":{}}