A combined Lagrangian, linear programming, and implication heuristic for large-scale set partitioning problems

DOI10.1007/BF00127080zbMath0857.90089OpenAlexW1977000744MaRDI QIDQ1922639

Atamtürk, Alper, Nemhauser, George I., Savelsbergh, Martin W. P.

Publication date: 1 September 1996

Published in: Journal of Heuristics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00127080

zbMATH Keywords

approximation algorithmcutting planesset partitioningpreprocessingcost perturbationsLagrangian dual frameworkproblem size-reduction

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Integer programming (90C10) Linear programming (90C05)

Related Items

SDP-Based Bounds for the Quadratic Cycle Cover Problem via Cutting-Plane Augmented Lagrangian Methods and Reinforcement Learning, Exploiting variable associations to configure efficient local search algorithms in large-scale binary integer programs, Conflict graphs in solving integer programming problems, A relax-and-cut algorithm for the set partitioning problem, A dual ascent procedure for the set partitioning problem, Modelling transfer line design problem via a set partitioning problem, VERY STRONGLY CONSTRAINED PROBLEMS: AN ANT COLONY OPTIMIZATION APPROACH, Hybridizing exact methods and metaheuristics: a taxonomy, A concurrent processing framework for the set partitioning problem, The multiphase course timetabling problem

Uses Software

• MIPLIB
• MINTO

Cites Work

• MINTO, a Mixed INTeger Optimizer
• An algorithm for large scale 0-1 integer programming with application to airline crew scheduling
• Branch-and-Price: Column Generation for Solving Huge Integer Programs
• Optimal Solution of Set Covering/Partitioning Problems Using Dual Heuristics
• Set Partitioning: A survey
• Solving Airline Crew Scheduling Problems by Branch-and-Cut
• Preprocessing and Probing Techniques for Mixed Integer Programming Problems
• On the facial structure of set packing polyhedra
• The Set-Partitioning Problem: Set Covering with Equality Constraints