View Related Documents

Abstract

We consider the integer single node flow problem with constant lower and upper bounds on the variables. This problem arises as subproblem of more general mixed integer problems such as lotsizing problems. A complete description of the convex hull of the feasible solution set is given. This description is based on families of valid inequalities whose coefficients are obtained from the coefficients of the facet-defining inequalities for the convex hull of integer knapsack sets with two variables. All the coefficients can be computed in polynomial time in the size of the input data. We present polynomial separation algorithms and an extended formulation.
Received: April, 2004

Fulltext Preview

Image of the first page of the fulltext document