On the effectiveness of the linear programming relaxation of the 0-1 multi-commodity minimum cost network flow problem
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Choi, Dae-Sik | - |
dc.contributor.author | Choi, In-Chan | - |
dc.date.accessioned | 2021-09-09T06:44:49Z | - |
dc.date.available | 2021-09-09T06:44:49Z | - |
dc.date.created | 2021-06-19 | - |
dc.date.issued | 2006 | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.uri | https://scholar.korea.ac.kr/handle/2021.sw.korea/123198 | - |
dc.description.abstract | Several studies have reported that the linear program relaxation of integer multi-commodity network flow problems often provides integer optimal solutions. We explore this phenomenon with a 0-1 multi-commodity network with mutual arc capacity constraints. Characteristics of basic solutions in the linear programming relaxation problem of the 0-1 multi-commodity problem are identified. Specifically, necessary conditions for a linear programming relaxation to have a non-integer solution are presented. Based on the observed characteristics, a simple illustrative example problem is constructed to show that its LP relaxation problem has integer optimal solutions with a relatively high probability. Furthermore, to investigate whether or not and under what conditions this tendency applies to large-sized problems, we have carried out computational experiments by using randomly generated problem instances. The results of our computational experiment indicate that there exists a narrow band of arc density in which the 0-1 multi-commodity problems possess no integer optimal solutions. | - |
dc.language | English | - |
dc.language.iso | en | - |
dc.publisher | SPRINGER-VERLAG BERLIN | - |
dc.subject | CONSTRAINTS | - |
dc.title | On the effectiveness of the linear programming relaxation of the 0-1 multi-commodity minimum cost network flow problem | - |
dc.type | Article | - |
dc.contributor.affiliatedAuthor | Choi, In-Chan | - |
dc.identifier.wosid | 000240077300054 | - |
dc.identifier.bibliographicCitation | COMPUTING AND COMBINATORICS, PROCEEDINGS, v.4112, pp.517 - 526 | - |
dc.relation.isPartOf | COMPUTING AND COMBINATORICS, PROCEEDINGS | - |
dc.citation.title | COMPUTING AND COMBINATORICS, PROCEEDINGS | - |
dc.citation.volume | 4112 | - |
dc.citation.startPage | 517 | - |
dc.citation.endPage | 526 | - |
dc.type.rims | ART | - |
dc.type.docType | Article; Proceedings Paper | - |
dc.description.journalClass | 1 | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
dc.relation.journalResearchArea | Computer Science | - |
dc.relation.journalResearchArea | Mathematics | - |
dc.relation.journalWebOfScienceCategory | Computer Science, Theory & Methods | - |
dc.relation.journalWebOfScienceCategory | Mathematics | - |
dc.subject.keywordPlus | CONSTRAINTS | - |
dc.subject.keywordAuthor | optimization | - |
dc.subject.keywordAuthor | multi-commodity | - |
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
(02841) 서울특별시 성북구 안암로 14502-3290-1114
COPYRIGHT © 2021 Korea University. All Rights Reserved.
Certain data included herein are derived from the © Web of Science of Clarivate Analytics. All rights reserved.
You may not copy or re-distribute this material in whole or in part without the prior written consent of Clarivate Analytics.