The flow set with partial order is a mixed-integer set described by a budget on total flow and a partial order on the arcs that may carry positive flow. This set is a common substructure of resource allocation and scheduling problems with precedence constraints and robust network flow problems under demand/capacity uncertainty. We give a polyhedral analysis of the convex hull of the flow set with partial order. Unlike for the flow set without partial order, cover-type inequalities based on partial order structure are a function of a lifting sequence. We study the lifting sequences and describe structural results on the lifting coefficients for general and simpler special cases. We show that lifting coefficients can be computed by solving maximum weight closure problems in general. For the special case of induced-minimal covers, we give a sequence-dependent characterization of the lifting coefficients. We prove, however, if the partial order is defined by an arborescence, then lifting is sequence-independent and all lifting coefficients can be computed in linear time. On the other hand, if the partial order is defined by a path (total order), then the coefficients can be expressed explicitly. We also give a complete polyhedral description of the flow set with partial order for the polynomially-solvable total order case. We show that finding an optimal lifting order for a given induced-minimal cover and a given fractional solution is a submodular optimization problem, which is solved greedily. Finally, we present preliminary computational results with a cutting-plane algorithm based on the lifting and separation results.
Citation
Appeared in Mathematics of Operations Research. Check http://www.ieor.berkeley.edu/~atamturk/