Minimum concave-cost network flow problems: Applications,complexity, and algorithms |
| |
Authors: | G. M. Guisewite P. M. Pardalos |
| |
Affiliation: | (1) HRB Systems, 16804 State College, PA, USA;(2) Department of Computer Science, Pennsylvania State University, 16802 University Park, PA, USA |
| |
Abstract: | We discuss a wide range of results for minimum concave-cost network flow problems, including related applications, complexity issues, and solution techniques. Applications from production and inventory planning, and transportation and communication network design are discussed. New complexity results are proved which show that this problem is NP-hard for cases with cost functions other than fixed charge. An overview of solution techniques for this problem is presented, with some new results given regarding the implementation of a particular branch-and-bound approach. |
| |
Keywords: | Concave-cost network flow global optimization complexity theory NP-hard transportation problems |
本文献已被 SpringerLink 等数据库收录! |
|