| Some Classes of Valid Inequalities and Convex Hull Characterizations for *corresponding author Dynamic Fixed-charge Problems under Nested Constraints (2008) | |||||||||||||||
Abstract | |||||||||||||||
| 0094462. The authors also gratefully acknowledge the detailed comments of two anonymous referees regarding relationships with lot-sizing problems. This paper studies the polyhedral structure of dynamic fixed-charge problems that have nested relationships constraining the flow or activity variables. Constraints of this type might typically arise in hierarchical or multi-period models and capacitated lot-sizing problems, but might also be induced among choices of key variables via an LP-based post-optimality analysis. We characterize several classes of valid inequalities and inductively derive convex hull representations in a higher dimensional space using lifting constructs based on the Reformulation-Linearization Technique. Relationships with certain known classes of valid inequalities for single item capacitated lot-sizing problems are also identified. Keywords: Dynamic fixed-charge problems, capacitated lot-sizing, Reformulation-linearization Technique, valid inequalities, convex hull. ii Fixed-charge problems, notably including network flow and facility location fixed-charge problems, occupy a central place among classical mixed-integer programming models. An extensive literature of practical applications and of proposed solution procedures has emerged, attesting to the importance and challenge of this class of problems. Applications include natural | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||