Campuses:

A special case of the integer single node flow set with upper bounds

Monday, July 25, 2005 - 11:15am - 12:00pm
EE/CS 3-180
Miguel Constantino (University of Lisbon)
In this talk we discuss the polyhedral structure of the convex hull of the integer single node flow set with two possible values for the upper bounds on the arc flows. These mixed integer sets may arise as substructure of more complex mixed integer sets that model the feasible solutions of real application problems such as network design, location and lotsizing. We give a complete description of this special integer single node flow polyhedron based on the generalization of the description of the integer single node flow polyhedron with two arcs. All the coefficients of the facet-defining inequalities can be computed in polynomial time adapting a known algorithm from Hirschberg and Wong (1976) for the two integer knapsack problem. We report on computational experience.

Joint work with Agostinho Agra.