Tighter representations for set partitioning problems

DOI10.1016/0166-218X(95)00060-5MaRDI QIDQ1917353zbMATH OpenOpenAlexFDO

Authors Hanif D. Sherali, Youngho Lee

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)

Recommendations

• Reformulation of the set partitioning problem as a pure network with special order set constraints
• A network relaxation based enumeration algorithm for set partitioning
• The matching relaxation for a class of generalized set partitioning problems
• Properties of some ILP formulations of a class of partitioning problems
• Cutting planes for RLT relaxations of mixed 0-1 polynomial programs

Cites work

• scientific article; zbMATH DE number 3561085 (Why is no real title available?)
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A Multiplier Adjustment Approach for the Set Partitioning Problem
• A Tight Linearization and an Algorithm for Zero-One Quadratic 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
• An Algorithm for Large Set Partitioning Problems
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Mixed-integer bilinear programming problems
• On the Set-Covering Problem: II. An Algorithm for Set Partitioning
• Optimal Solution of Set Covering/Partitioning Problems Using Dual Heuristics
• Optimal set partitioning, matchings and lagrangian duality
• Set Partitioning: A survey
• The Set-Partitioning Problem: Set Covering with Equality Constraints

Cited in

(19)

• A relax-and-cut algorithm for the set partitioning problem
• RLT insights into lift-and-project closures
• On the polyhedral lift-and-project methods and the fractional stable set polytope
• Cutting planes for RLT relaxations of mixed 0-1 polynomial programs
• Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs
• A concurrent processing framework for the set partitioning problem
• Complementary column generation and bounding approaches for set partitioning formulations
• Surrogate-RLT cuts for zero-one integer programs
• 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
• Compact linearization for binary quadratic problems
• Breaking the rectangle bound barrier against formula size lower bounds
• Valid Inequalities and Separation Algorithms for the Set Partitioning Problem
• Exploring the limits of subadditive approaches: parallels between optimization and complexity theory
• A comprehensive analysis of polyhedral lift-and-project methods
• The matching relaxation for a class of generalized set partitioning problems
• Set packing relaxations of some integer programs
• On the complete set packing and set partitioning polytopes: properties and rank 1 facets
• Optimal set-partitioning based on group quality likelihood using partition-growing algorithm

This page was built for publication: Tighter representations for set partitioning problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1917353)