  


The Flow Set with Partial Order
Alper Atamturk (atamturkberkeley.edu) Abstract: The flow set with partial order is a mixedinteger 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, covertype 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 inducedminimal covers, we give a sequencedependent characterization of the lifting coefficients. We prove, however, if the partial order is defined by an arborescence, then lifting is sequenceindependent 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 polynomiallysolvable total order case. We show that finding an optimal lifting order for a given inducedminimal cover and a given fractional solution is a submodular optimization problem, which is solved greedily. Finally, we present preliminary computational results with a cuttingplane algorithm based on the lifting and separation results. Keywords: Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Category 2: Integer Programming (Cutting Plane Approaches ) Citation: Appeared in Mathematics of Operations Research. Check http://www.ieor.berkeley.edu/~atamturk/ Download: Entry Submitted: 06/26/2007 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  