A Lagrangian-based heuristic for large-scale set covering problems

DOI10.1007/BF01581106zbMath0919.90085OpenAlexW2091836882MaRDI QIDQ1290617

Antonio Sassano, Sebastián Ceria, Paolo Nobili

Publication date: 5 September 1999

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

approximate solutions0-1 programmingrailwayssubgradient algorithmscrew-schedulingItalian railwaysLagrangian-based heuristiclarge-scale set-covering problemsprimal-dual Lagrangian

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Deterministic scheduling theory in operations research (90B35) Boolean programming (90C09)

Related Items

Dissecting the duality gap: the supporting hyperplane interpretation revisited, The fixed charge transportation problem: a strong formulation based on Lagrangian decomposition and column generation, On some difficult linear programs coming from set partitioning, Two-phase method and Lagrangian relaxation to solve the bi-objective set covering problem, An efficient local search heuristic with row weighting for the unicost set covering problem, An effective and simple heuristic for the set covering problem, Relaxation heuristics for the set multicover problem with generalized upper bound constraints, Algorithms for railway crew management, Cutting plane versus compact formulations for uncertain (integer) linear programs, Solving large set covering problems for crew scheduling, A binary cat swarm optimization algorithm for the non-unicost set covering problem, A theoretical justification of the set covering greedy heuristic of Caprara et al., A hybrid heuristic for the set covering problem, Matheuristics: survey and synthesis, Covering models and optimization techniques for emergency response facility location and planning: a review, Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism, Efficient heuristics for a partial set covering problem with mutually exclusive pairs of facilities, The Impact of a New Formulation When Solving the Set Covering Problem Using the ACO Metaheuristic, Improved handling of uncertainty and robustness in set covering problems, Exploiting variable associations to configure efficient local search algorithms in large-scale binary integer programs, A binary monkey search algorithm variation for solving the set covering problem, Constrained 0-1 quadratic programming: basic approaches and extensions, An improved configuration checking-based algorithm for the unicost set covering problem, A heuristic algorithm for the set covering problem, A matheuristic based on Lagrangian relaxation for the multi-activity shift scheduling problem, A mixed integer linear program and tabu search approach for the complementary edge covering problem, A dual ascent heuristic for obtaining a lower bound of the generalized set partitioning problem with convexity constraints, A 3-flip neighborhood local search for the set covering problem, Surrogate constraint normalization for the set covering problem, An efficient mean field approach to the set covering problem, Avoiding redundant columns by adding classical Benders cuts to column generation subproblems, Computational experience with general cutting planes for the set covering problem, The set covering problem revisited: an empirical study of the value of dual information, Model-based view planning, Efficient feature selection for logical analysis of large-scale multi-class datasets, On Multiple Coverings of Fixed Size Containers with Non-Euclidean Metric by Circles of Two Types, Heuristics for the variable sized bin-packing problem, A new approach for solving set covering problem using jumping particle swarm optimization method, Solving the non-unicost set covering problem by using cuckoo search and black hole optimization, An adaptation of SH heuristic to the location set covering problem, A feasibility-ensured Lagrangian heuristic for general decomposable problems, Exploring further advantages in an alternative formulation for the set covering problem, Primal convergence from dual subgradient methods for convex optimization, Column generation extensions of set covering greedy heuristics

Cites Work

• Unnamed Item
• A new approach for crew pairing problems by column generation with an application to air transportation
• A probabilistic heuristic for a computationally difficult set covering problem
• Optimal Solution of Set Covering/Partitioning Problems Using Dual Heuristics
• Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
• A Greedy Heuristic for the Set-Covering Problem
• Solving Airline Crew Scheduling Problems by Branch-and-Cut
• A Dynamic Subgradient-Based Branch-and-Bound Procedure for Set Covering