WEKO3
アイテム
{"_buckets": {"deposit": "d446977b-6624-4d05-9432-f893f8a949ff"}, "_deposit": {"id": "53258", "owners": [], "pid": {"revision_id": 0, "type": "depid", "value": "53258"}, "status": "published"}, "_oai": {"id": "oai:tsukuba.repo.nii.ac.jp:00053258", "sets": ["6908", "2023"]}, "item_5_biblio_info_6": {"attribute_name": "書誌情報", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "2019-09", "bibliographicIssueDateType": "Issued"}, "bibliographicIssueNumber": "1", "bibliographicPageEnd": "176", "bibliographicPageStart": "143", "bibliographicVolumeNumber": "74", "bibliographic_titles": [{"bibliographic_title": "Computational optimization and applications"}]}]}, "item_5_description_4": {"attribute_name": "抄録", "attribute_value_mlt": [{"subitem_description": "We apply novel inner-iteration preconditioned Krylov subspace methods to the interior-point algorithm for linear programming (LP). Inner-iteration preconditioners recently proposed by Morikuni and Hayami enable us to overcome the severe ill-conditioning of linear equations solved in the final phase of interior-point iterations. The Krylov subspace methods do not suffer from rank-deficiency and therefore no preprocessing is necessary even if rows of the constraint matrix are not linearly independent. By means of these methods, a new interior-point recurrence is proposed in order to omit one matrix-vector product at each step. Extensive numerical experiments are conducted over diverse instances of 140 LP problems including the Netlib, QAPLIB, Mittelmann and Atomizer Basis Pursuit collections. The largest problem has 434,580 unknowns. It turns out that our implementation is more robust than the standard public domain solvers SeDuMi (Self-Dual Minimization), SDPT3 (Semidefinite Programming Toh-Todd-Tütüncü) and the LSMR iterative solver in PDCO (Primal-Dual Barrier Method for Convex Objectives) without increasing CPU time. The proposed interior-point method based on iterative solvers succeeds in solving a fairly large number of LP instances from benchmark libraries under the standard stopping criteria. The work also presents a fairly extensive benchmark test for several renowned solvers including direct and iterative solvers.", "subitem_description_type": "Abstract"}]}, "item_5_publisher_27": {"attribute_name": "出版者", "attribute_value_mlt": [{"subitem_publisher": "Springer"}]}, "item_5_relation_11": {"attribute_name": "DOI", "attribute_value_mlt": [{"subitem_relation_type_id": {"subitem_relation_type_id_text": "10.1007/s10589-019-00103-y", "subitem_relation_type_select": "DOI"}}]}, "item_5_rights_12": {"attribute_name": "権利", "attribute_value_mlt": [{"subitem_rights": "© The Author(s) 2019"}, {"subitem_rights": "Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made."}]}, "item_5_select_15": {"attribute_name": "著者版フラグ", "attribute_value_mlt": [{"subitem_select_item": "publisher"}]}, "item_5_source_id_7": {"attribute_name": "ISSN", "attribute_value_mlt": [{"subitem_source_identifier": "0926-6003", "subitem_source_identifier_type": "ISSN"}]}, "item_5_source_id_9": {"attribute_name": "書誌レコードID", "attribute_value_mlt": [{"subitem_source_identifier": "AA10936780", "subitem_source_identifier_type": "NCID"}]}, "item_creator": {"attribute_name": "著者", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "保國, 惠一"}, {"creatorName": "モリクニ, ケイイチ", "creatorNameLang": "ja-Kana"}, {"creatorName": "MORIKUNI, Keiichi", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "196858", "nameIdentifierScheme": "WEKO"}, {"nameIdentifier": "90765934", "nameIdentifierScheme": "e-Rad", "nameIdentifierURI": "https://nrid.nii.ac.jp/ja/nrid/1000090765934"}, {"nameIdentifier": "0000003789", "nameIdentifierScheme": "筑波大学研究者総覧", "nameIdentifierURI": "http://trios.tsukuba.ac.jp/researcher/0000003789"}]}, {"creatorNames": [{"creatorName": "Cui, Yiran", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "216480", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "Tsuchiya, Takashi", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "216481", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "Hayami, Ken", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "216482", "nameIdentifierScheme": "WEKO"}]}]}, "item_files": {"attribute_name": "ファイル情報", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2019-11-25"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "COA_74-1.pdf", "filesize": [{"value": "933.7 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_6", "mimetype": "application/pdf", "size": 933700.0, "url": {"label": "COA_74-1", "url": "https://tsukuba.repo.nii.ac.jp/record/53258/files/COA_74-1.pdf"}, "version_id": "5402e8bd-e231-49ca-8c69-3c16cff075db"}]}, "item_language": {"attribute_name": "言語", "attribute_value_mlt": [{"subitem_language": "eng"}]}, "item_resource_type": {"attribute_name": "資源タイプ", "attribute_value_mlt": [{"resourcetype": "journal article", "resourceuri": "http://purl.org/coar/resource_type/c_6501"}]}, "item_title": "Implementation of interior-point methods for LP based on Krylov subspace iterative solvers with inner-iteration preconditioning", "item_titles": {"attribute_name": "タイトル", "attribute_value_mlt": [{"subitem_title": "Implementation of interior-point methods for LP based on Krylov subspace iterative solvers with inner-iteration preconditioning"}]}, "item_type_id": "5", "owner": "1", "path": ["6908", "2023"], "permalink_uri": "http://hdl.handle.net/2241/00158675", "pubdate": {"attribute_name": "公開日", "attribute_value": "2019-11-25"}, "publish_date": "2019-11-25", "publish_status": "0", "recid": "53258", "relation": {}, "relation_version_is_last": true, "title": ["Implementation of interior-point methods for LP based on Krylov subspace iterative solvers with inner-iteration preconditioning"], "weko_shared_id": 5}
Implementation of interior-point methods for LP based on Krylov subspace iterative solvers with inner-iteration preconditioning
http://hdl.handle.net/2241/00158675
http://hdl.handle.net/2241/001586758333009d-c5b7-4622-b0b5-9dbb4b210867
名前 / ファイル | ライセンス | アクション |
---|---|---|
COA_74-1 (933.7 kB)
|
Item type | Journal Article(1) | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
公開日 | 2019-11-25 | |||||||||||
タイトル | ||||||||||||
タイトル | Implementation of interior-point methods for LP based on Krylov subspace iterative solvers with inner-iteration preconditioning | |||||||||||
言語 | ||||||||||||
言語 | eng | |||||||||||
資源タイプ | ||||||||||||
資源 | http://purl.org/coar/resource_type/c_6501 | |||||||||||
タイプ | journal article | |||||||||||
著者 |
保國, 惠一
× 保國, 惠一
WEKO
196858
× Cui, Yiran× Tsuchiya, Takashi× Hayami, Ken |
|||||||||||
抄録 | ||||||||||||
内容記述タイプ | Abstract | |||||||||||
内容記述 | We apply novel inner-iteration preconditioned Krylov subspace methods to the interior-point algorithm for linear programming (LP). Inner-iteration preconditioners recently proposed by Morikuni and Hayami enable us to overcome the severe ill-conditioning of linear equations solved in the final phase of interior-point iterations. The Krylov subspace methods do not suffer from rank-deficiency and therefore no preprocessing is necessary even if rows of the constraint matrix are not linearly independent. By means of these methods, a new interior-point recurrence is proposed in order to omit one matrix-vector product at each step. Extensive numerical experiments are conducted over diverse instances of 140 LP problems including the Netlib, QAPLIB, Mittelmann and Atomizer Basis Pursuit collections. The largest problem has 434,580 unknowns. It turns out that our implementation is more robust than the standard public domain solvers SeDuMi (Self-Dual Minimization), SDPT3 (Semidefinite Programming Toh-Todd-Tütüncü) and the LSMR iterative solver in PDCO (Primal-Dual Barrier Method for Convex Objectives) without increasing CPU time. The proposed interior-point method based on iterative solvers succeeds in solving a fairly large number of LP instances from benchmark libraries under the standard stopping criteria. The work also presents a fairly extensive benchmark test for several renowned solvers including direct and iterative solvers. | |||||||||||
書誌情報 |
Computational optimization and applications 巻 74, 号 1, p. 143-176, 発行日 2019-09 |
|||||||||||
ISSN | ||||||||||||
収録物識別子タイプ | ISSN | |||||||||||
収録物識別子 | 0926-6003 | |||||||||||
書誌レコードID | ||||||||||||
収録物識別子タイプ | NCID | |||||||||||
収録物識別子 | AA10936780 | |||||||||||
DOI | ||||||||||||
識別子タイプ | DOI | |||||||||||
関連識別子 | 10.1007/s10589-019-00103-y | |||||||||||
権利 | ||||||||||||
権利情報 | © The Author(s) 2019 | |||||||||||
権利 | ||||||||||||
権利情報 | Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. | |||||||||||
著者版フラグ | ||||||||||||
値 | publisher | |||||||||||
出版者 | ||||||||||||
出版者 | Springer |