Tighter representations for set partitioning problems

DOI10.1016/0166-218X(95)00060-5zbMath0846.90077OpenAlexW2025605614MaRDI QIDQ1917353

Youngho Lee, Hanif D. Sherali

Publication date: 7 July 1996

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(95)00060-5

zbMATH Keywords

cutting planesvalid inequalitiesreformulation-linearization techniquehierarchy of relaxationsset partitioning polytope

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Boolean programming (90C09)

Related Items

Surrogate-RLT cuts for zero-one integer programs, On the complete set packing and set partitioning polytopes: properties and rank 1 facets, Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory, Reduced first-level representations via the reformulation-linearization technique: Results, counterexamples, and computations, Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra, A relax-and-cut algorithm for the set partitioning problem, Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs, Compact linearization for binary quadratic problems, BREAKING THE RECTANGLE BOUND BARRIER AGAINST FORMULA SIZE LOWER BOUNDS, RLT insights into lift-and-project closures, A Comprehensive Analysis of Polyhedral Lift-and-Project Methods, Complementary column generation and bounding approaches for set partitioning formulations, On the polyhedral lift-and-project methods and the fractional stable set polytope, Cutting planes for RLT relaxations of mixed 0-1 polynomial programs, A concurrent processing framework for the set partitioning problem, OPTIMAL SET-PARTITIONING BASED ON GROUP QUALITY LIKELIHOOD USING PARTITION-GROWING ALGORITHM

Cites Work

• Unnamed Item
• Mixed-integer bilinear programming problems
• A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Optimal Solution of Set Covering/Partitioning Problems Using Dual Heuristics
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Optimal set partitioning, matchings and lagrangian duality
• A Multiplier Adjustment Approach for the Set Partitioning Problem
• An Algorithm for Large Set Partitioning Problems
• On the Set-Covering Problem: II. An Algorithm for Set Partitioning
• Set Partitioning: A survey
• The Set-Partitioning Problem: Set Covering with Equality Constraints