The column subtraction algorithm: An exact method for solving weighted set covering, packing and partitioning problems

DOI10.1016/0305-0548(94)90083-3zbMath0810.90107OpenAlexW2075049669MaRDI QIDQ1333026

Farid Harche, Gerald L. Thompson

Publication date: 13 September 1994

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

Full work available at URL: https://doi.org/10.1016/0305-0548(94)90083-3

zbMATH Keywords

partitioningexact solutionspackingcolumn subtractionlarge set covering

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Combinatorial optimization (90C27)

Related Items

A weight-balanced branching rule for SAT, A dual ascent procedure for the set partitioning problem, A genetic algorithm for the set covering problem, Backtracking tactics in the backtrack method for SAT, 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
• Unnamed Item
• Unnamed Item
• On the set covering polytope. II: Lifting the facets with coefficients in \(\{\) 0,1,2\(\}\)
• On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\)
• On the 0,1 facets of the set covering polytope
• On the facial structure of the set covering polytope
• An algorithm for set covering problem
• Optimal Solution of Set Covering/Partitioning Problems Using Dual Heuristics
• Cutting planes from conditional bounds: A new approach to set covering
• Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
• An Algorithm for the Three-Index Assignment Problem
• An Algorithm for Large Set Partitioning Problems
• Note—A Computational Survey of Methods for the Set Covering Problem
• On the Set-Covering Problem: II. An Algorithm for Set Partitioning
• Set Partitioning: A survey
• The Set-Covering Problem: A New Implicit Enumeration Algorithm
• The pivot and probe algorithm for solving a linear program
• Letter to the Editor—The Multidimensional Assignment Problem
• The Set-Partitioning Problem: Set Covering with Equality Constraints
• An Additive Algorithm for Solving Linear Programs with Zero-One Variables
• Set Covering by Single-Branch Enumeration with Linear-Programming Subproblems
• On the Set-Covering Problem
• Improved Combinatorial Programming Algorithms for a Class of All-Zero-One Integer Programming Problems
• Set Covering by an All Integer Algorithm