A relax-and-cut algorithm for the set partitioning problem

DOI10.1016/j.cor.2006.10.009zbMath1139.90034OpenAlexW2090941829MaRDI QIDQ2462542

Victor F. Cavalcante, Abilio Lucena, Cid Carvalho De Souza

Publication date: 30 November 2007

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2006.10.009

zbMATH Keywords

Lagrangian relaxationcutting planesset partitioningrelax-and-cut algorithms

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items (5)

The matching relaxation for a class of generalized set partitioning problems ⋮ Exact algorithms for the vertex separator problem in graphs ⋮ Searching for optimal integer solutions to set partitioning problems using column generation ⋮ Lagrangian heuristics for the quadratic knapsack problem ⋮ OPTIMAL SET-PARTITIONING BASED ON GROUP QUALITY LIKELIHOOD USING PARTITION-GROWING ALGORITHM

Uses Software

• XPRESS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Non delayed relax-and-cut algorithms
• Computational experience with approximation algorithms for the set covering problem
• A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships
• A surrogate heuristic for set covering problems
• Stronger \(K\)-tree relaxations for the vehicle routing problem
• Tighter representations for set partitioning problems
• A combined Lagrangian, linear programming, and implication heuristic for large-scale set partitioning problems
• Constraint handling in genetic algorithms: the set partitioning problem
• Surrogate Dual Multiplier Search Procedures in Integer Programming
• Optimal Solution of Set Covering/Partitioning Problems Using Dual Heuristics
• Using Surrogate Constraints in a Lagrangian Relaxation Approach to Set-Covering Problems
• Some relationships between lagrangian and surrogate duality in integer programming
• Technical Note—Searchability of the Composite and Multiple Surrogate Dual Functions
• Surrogate duality in a branch-and-bound procedure
• A restricted Lagrangean approach to the traveling salesman problem
• A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
• Surrogate Constraint Duality in Mathematical Programming
• Solving Airline Crew Scheduling Problems by Branch-and-Cut
• Optimal rectangular partitions
• A Heuristic Method for the Set Covering Problem
• On the facial structure of set packing polyhedra
• Surrogate Mathematical Programming

This page was built for publication: A relax-and-cut algorithm for the set partitioning problem