Semi-continuous network flow problems

• 成果类型: Article
• 署名作者: Angulo, Gustavo; Ahmed, Shabbir; Dey, Santanu S.
• 署名单位: University System of Georgia; Georgia Institute of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-013-0675-7
• 发表日期: 2014
• 页码: 565-599
• 关键词: Optimization; industry

摘要

We consider semi-continuous network flow problems, that is, a class of network flow problems where some of the variables are restricted to be semi-continuous. We introduce the semi-continuous inflow set with variable upper bounds as a relaxation of general semi-continuous network flow problems. Two particular cases of this set are considered, for which we present complete descriptions of the convex hull in terms of linear inequalities and extended formulations. We consider a class of semi-continuous transportation problems where inflow systems arise as substructures, for which we investigate complexity questions. Finally, we study the computational efficacy of the developed polyhedral results in solving randomly generated instances of semi-continuous transportation problems.