Semi-continuous network flow problems (Q2248765)

The authors consider network flow problems in which some variables are semi-continuous, i.e. take values in a set of the form \(\{0\} \cup [l,u]\) for some \(0 \leq l \leq u\). They define the semi-continuous inflow set \(S(t,h)\), which arises as a substructure in general semi-continuous network flow problems. They show that optimizing a linear function over \(S(t,h)\) is NP-hard, even if \(l=0\) and present some basic polyhedral results, such as full dimensionality of \(S(t,h)\) and facet defining inequalities for the polyhedron \(conv(S(t,h))\). For the sepcial cases of \(t=0\) and \(h=0\), they provide complete descriptions of the convex hull. Finally, they consider a semi-continuous transportation problem, for which they investigate complexity questions. They present numerical results that show the effectiveness of the polyhedral results on randomly generated instances of this problem.