Back to Search
Start Over
Valid Inequalities for Problems with Additive Variable Upper Bounds.
- Source :
- Integer Programming & Combinatorial Optimization (9783540660194); 1999, p60-72, 13p
- Publication Year :
- 1999
-
Abstract
- We study the facial structure of a polyhedron associated with the single node relaxation of network flow problems with additive variable upper bounds. This type of structure arises, for example, in network design/expansion problems and in production planning problems with setup times. We first derive two classes of valid inequalities for this polyhedron and give the conditions under which they are facet-defining. Then we generalize our results through sequence independent lifting of valid inequalities for lower-dimensional projections. Our computational experience with large network expansion problems indicates that these inequalities are very effective in improving the quality of the linear programming relaxations. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783540660194
- Database :
- Supplemental Index
- Journal :
- Integer Programming & Combinatorial Optimization (9783540660194)
- Publication Type :
- Book
- Accession number :
- 33100500
- Full Text :
- https://doi.org/10.1007/3-540-48777-8_5