Optimization Online


Semi-continuous network flow problems

Gustavo Angulo(gangulo***at***gatech.edu)
Shabbir Ahmed(sahmed***at***isye.gatech.edu)
Santanu S. Dey(sdey***at***isye.gatech.edu)

Abstract: 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.

Keywords: Mixed-integer programming, network flow problems, semi-continuous variables

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Network Optimization


Download: [PDF]

Entry Submitted: 04/26/2012
Entry Accepted: 04/27/2012
Entry Last Modified: 04/26/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society