On some difficult linear programs coming from set partitioning

DOI10.1016/S0166-218X(01)00252-9zbMath0995.90069MaRDI QIDQ1348247

Francisco Barahona, Ranga Anbil

Publication date: 15 May 2002

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

zbMATH Keywords

volume algorithmsubgradient algorithmlarge scale linear progamming

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Linear programming (90C05) Methods of reduced gradient type (90C52)

Related Items

Unnamed Item ⋮ A hybrid soft computing approach for subset problems ⋮ A dual ascent procedure for the set partitioning problem ⋮ Searching for optimal integer solutions to set partitioning problems using column generation ⋮ A dual ascent heuristic for obtaining a lower bound of the generalized set partitioning problem with convexity constraints ⋮ Two ``well-known properties of subgradient optimization ⋮ Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut ⋮ OPTIMAL SET-PARTITIONING BASED ON GROUP QUALITY LIKELIHOOD USING PARTITION-GROWING ALGORITHM ⋮ Rapid prototyping of optimization algorithms using COIN-OR: a case study involving the cutting-stock problem

Uses Software

• OSL

Cites Work

• On the choice of step size in subgradient optimization
• Variable target value subgradient method
• A Lagrangian-based heuristic for large-scale set covering problems
• The volume algorithm: Producing primal solutions with a subgradient method
• Accelerating the convergence of subgradient optimisation
• The Efficiency of Ballstep Subgradient Level Methods for Convex Optimization
• A generalization of Polyak's convergence result for subgradient optimization
• Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
• On convergence rates of subgradient optimization methods
• The Set-Covering Problem: A New Implicit Enumeration Algorithm
• A global approach to crew-pairing optimization
• Validation of subgradient optimization
• The Efficiency of Subgradient Projection Methods for Convex Optimization, Part II: Implementations and Extensions
• A Heuristic Method for the Set Covering Problem
• The Traveling-Salesman Problem and Minimum Spanning Trees
• Minimization of unsmooth functionals
• The traveling-salesman problem and minimum spanning trees: Part II
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item