A probabilistic heuristic for a computationally difficult set covering problem

DOI10.1016/0167-6377(89)90002-3zbMath0675.90073OpenAlexW2028438572MaRDI QIDQ1122493

Thomas A. Feo, Mauricio G. C. Resende

Publication date: 1989

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(89)90002-3

zbMATH Keywords

incidence matrices Steiner triple systems greedy approach probabilistic set covering heuristic

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Triple systems (05B07)

Related Items

GRASP algorithms for the robust railway network design problem, ParadisEO-MO: from fitness landscape analysis to efficient local search algorithms, A tabu search experience in production scheduling, Vehicle routing problems with time windows and multiple service workers: a systematic comparison between ACO and GRASP, Multiobjective GRASP with path relinking, Stability evaluation of a railway timetable at station level, Investigation of a new GRASP-based clustering algorithm applied to biological data, Logic based methods for SNPs tagging and reconstruction, The electrical distribution network planning problem, Solution approaches for the vehicle routing problem with occasional drivers and time windows, A GRASP with penalty objective function for the green vehicle routing problem with private capacitated stations, Optimizing multiple qualifications of products on non-identical parallel machines, An algorithm for large scale 0-1 integer programming with application to airline crew scheduling, Packing items to feed assembly lines, Solving two location models with few facilities by using a hybrid heuristic: a real health resources case, On some optimization problems in molecular biology, Vehicle routing for milk collection with gradual blending: a case arising in Chile, Multi-machine energy-aware scheduling, Evolutionary, constructive and hybrid procedures for the bi-objective set packing problem, Evolution-inspired local improvement algorithm solving orienteering problem, Synchronizing vans and cargo bikes in a city distribution network, Problem space local search for number partitioning, Metaheuristics: A bibliography, Quota travelling salesman problem with passengers, incomplete ride and collection time optimization by ant-based algorithms, Solving hard set covering problems, Tabu search for the BWC problem, GRASP with strategic oscillation for the \(\alpha \)-neighbor \(p\)-center problem, Constructive-destructive heuristics for the safe set problem, Metaheuristics for the work‐troops scheduling problem, A hybrid heuristic approach to minimize number of tardy jobs in group technology systems, The constrained forward shortest path tour problem: Mathematical modeling and GRASP approximate solutions, Constraint Orbital Branching, Routing electric vehicles with a single recharge per route, Metaheuristics: A Canadian Perspective, An efficient compact quadratic convex reformulation for general integer quadratic programs, An enhanced GRASP approach for the index tracking problem, Strategic oscillation for the balanced minimum sum-of-squares clustering problem, A binary monkey search algorithm variation for solving the set covering problem, Storage Yard Management: Modelling and Solving, Efficient GRASP solution approach for the prisoner transportation problem, Exact and metaheuristic approaches to solve the integrated production scheduling, berth allocation and storage yard allocation problem, GRASP with path-relinking for the non-identical parallel machine scheduling problem with minimising total weighted completion times, Complexity among combinatorial problems from epidemics, A biased random-key genetic algorithm for data clustering, Intelligent water drops algorithm, Applications of the DM‐GRASP heuristic: a survey, Global optimization by continuous grasp, An improved configuration checking-based algorithm for the unicost set covering problem, Finding efficient make-to-order production and batch delivery schedules, Correspondence of projected 3-D points and lines using a continuous GRASP, Solving a bus driver scheduling problem with randomized multistart heuristics, Embedding signed graphs in the line, A multi-product production/distribution system design problem with direct shipments and lateral transshipments, A scatter search approach for the minimum sum-of-squares clustering problem, Improved heuristics for the regenerator location problem, A 3-flip neighborhood local search for the set covering problem, Minimizing labor requirements in a periodic vehicle loading problem, Variable neighbourhood search for the minimum labelling Steiner tree problem, Randomized heuristics for the Max-Cut problem, A hybrid heuristic for the diameter constrained minimum spanning tree problem, Solving large Steiner Triple Covering Problems, A branch-and-cut algorithm for partition coloring, Incremental bipartite drawing problem, A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems, Optimal selection of contracts and work shifts in multi-skill call centers, The set covering problem revisited: an empirical study of the value of dual information, Greedy randomized adaptive search procedures, Hybridizations of GRASP with path relinking for the far from most string problem, A research survey: review of flexible job shop scheduling techniques, A hybrid data mining metaheuristic for the p‐median problem, Heuristics and meta-heuristics for 2-layer straight line crossing minimization, An efficient exact approach for the constrained shortest path tour problem, A Branch-Price-and-Cut Procedure for the Discrete Ordered Median Problem, Bilinear Assignment Problem: Large Neighborhoods and Experimental Analysis of Algorithms, GRASP with Path-Relinking for Facility Layout, The ALGACEA‐1 method for the capacitated vehicle routing problem, Randomized heuristics for the family traveling salesperson problem, Un algorithme GRASP pour le problème de planification de techniciens et d'interventions pour les télécommunications, GRASP with path relinking heuristics for the antibandwidth problem, Metaheuristic approaches for the Berth Allocation Problem, A New Scatter Search Design for Multiobjective Combinatorial Optimization with an Application to Facility Location, A grasp for single machine scheduling with sequence dependent setup costs and linear delay penalties, Robust drone selective routing in humanitarian transportation network assessment, A set covering based matheuristic for a real‐world city logistics problem, Hybrid algorithms for placement of virtual machines across geo-separated data centers, Benders decomposition for the inventory vehicle routing problem with perishable products and environmental costs, A GRASP heuristic for the mixed Chinese postman problem, A GRASP and path relinking heuristic for rural road network development, Memetic algorithms, Evaluation of the Copycat Model for Predicting Complex Network Growth, Towards an efficient resolution of printing problems, Solving the traveling delivery person problem with limited computational time, An efficient GRASP-like algorithm for the multi-product straight pipeline scheduling problem, An exact algorithm for the maximum stable set problem, The food bank resource allocation problem, Metaheuristics for the distance constrained generalized covering traveling salesman problem, Improved solutions to the Steiner triple covering problem, A GRASP approach for the extended car sequencing problem, A combinatorial algorithm for the TDMA message scheduling problem, A review of recent advances in global optimization, Classification of applied methods of combinatorial optimization, Detecting robust cliques in graphs subject to uncertain edge failures, Exact and heuristic algorithms for the design of hub networks with multiple lines, An efficient local search heuristic with row weighting for the unicost set covering problem, Integer programming models for feature selection: new extensions and a randomized solution algorithm, Fast heuristics for the frequency channel assignment problem in multi-hop wireless networks, Advanced greedy randomized adaptive search procedure for the obnoxious \(p\)-median problem, Heuristics for the generalized median graph problem, An effective and simple heuristic for the set covering problem, Minimising maximum response time, A parallel hybrid greedy branch and bound scheme for the maximum distance-2 matching problem, A GRASP/path relinking algorithm for two- and three-dimensional multiple bin-size bin packing problems, A GRASP metaheuristic for microarray data analysis, A hybrid Lagrangean heuristic with GRASP and path-relinking for set \(k\)-covering, A hybrid column generation with GRASP and path relinking for the network load balancing problem, A hybrid data mining GRASP with path-relinking, A GRASP with path-relinking heuristic for the survivable IP/MPLS-over-WSON multi-layer network optimization problem, GRASP for the uncapacitated \(r\)-allocation \(p\)-hub median problem, A population-based metaheuristic for the pickup and delivery problem with time windows and LIFO loading, Intelligent-guided adaptive search for the maximum covering location problem, GRASP with exterior path-relinking and restricted local search for the multidimensional two-way number partitioning problem, A hybrid variable neighborhood search for the orienteering problem with mandatory visits and exclusionary constraints, Vector bin packing with heterogeneous bins: application to the machine reassignment problem, Carousel greedy: a generalized greedy algorithm with applications in optimization, Branch and bound for the cutwidth minimization problem, A nonmonotone GRASP, The constrained shortest path tour problem, The dynamic vehicle allocation problem with application in trucking companies in Brazil, A hybrid metaheuristic algorithm for the vehicle routing problem with stochastic demands, Heuristics for the mirrored traveling tournament problem, On the number of local minima for the multidimensional assignment problem, Improved modeling and solution methods for the multi-resource routing problem, Response time variability, A hybrid GRASP/VND algorithm for two- and three-dimensional bin packing, A variable neighborhood search algorithm for the multimode set covering problem, The design of a 0-1 integer optimizer and its application in the Carmen system, Multi-depot vessel routing problem in a direction dependent wavefield, A guided reactive GRASP for the capacitated multi-source Weber problem, Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking, A constraint programming approach to the additional relay placement problem in wireless sensor networks, Simulated annealing based GRASP for Pareto-optimal dissimilar paths problem, Exact and heuristic solutions to minimize total waiting time in the blood products distribution problem, Optimization of real-time multiserver system with two different channels and shortage of maintenance facilities., GRASP for set packing problems., GRASP and VNS for solving the \(p\)-next center problem, Logic classification and feature selection for biomedical data, A hybrid soft computing approach for subset problems, A GRASP heuristic for slab scheduling at continuous casters, An interior point algorithm to solve computationally difficult set covering problems, A GRASP for a difficult single machine scheduling problem, Reactive GRASP for the strip-packing problem, A survey on optimization metaheuristics, A discrete gravitational search algorithm for solving combinatorial optimization problems, Design of hybrids for the minimum sum-of-squares clustering problem, Enhancing an algorithm for set covering problems, Models and algorithms for reliability-oriented dial-a-ride with autonomous electric vehicles, Learnheuristics: hybridizing metaheuristics with machine learning for optimization with dynamic inputs, Extended GRASP for the job shop scheduling problem with total weighted tardiness objective, Scatter search for the bandpass problem, Avoiding local optima in the \(p\)-hub location problem using tabu search and GRASP, Restart strategies for GRASP with path-relinking heuristics, A biased random-key genetic algorithm for the Steiner triple covering problem, Scatter search for the cutwidth minimization problem, Efficient solutions for the far from most string problem, A GRASP algorithm for the closest string problem using a probability-based heuristic, A class of polynomially solvable 0-1 programming problems and an application, Efficient GRASP+VND and GRASP+VNS metaheuristics for the traveling repairman problem, Solving the response time variability problem by means of a psychoclonal approach, A path relinking approach for the team orienteering problem, Greedy random adaptive memory programming search for the capacitated clustering problem, Speeding up continuous GRASP, Surrogate constraint normalization for the set covering problem, Continuous GRASP with a local active-set method for bound-constrained global optimization, Efficient solutions for special zero-one programming problems, A novel list-constrained randomized VND approach in GPU for the traveling thief problem, Analysis of new variable selection methods for discriminant analysis, Heuristics for the bi-objective path dissimilarity problem, A mathematical program to refine gene regulatory networks, A bus driver scheduling problem: A new mathematical model and a GRASP approximate solution, GRASP with path-relinking for the generalized quadratic assignment problem, Queueing maximal covering location-allocation problem: an extension with \textit{M/G/1} queueing systems, GRASP and path relinking for the max-min diversity problem, Using a greedy random adaptative search procedure to solve the cover printing problem, A Lagrangian-based heuristic for large-scale set covering problems, GRASP heuristic with path-relinking for the multi-plant capacitated lot sizing problem, Exploring further advantages in an alternative formulation for the set covering problem, Heuristics for the flow line problem with setup costs, Algorithms for large scale set covering problems, Clustering heuristics for set covering, Real-time multiserver and multichannel systems with shortage of maintenance crews., A parallel genetic algorithm to solve the set-covering problem, Real-time system with homogeneous servers and nonidentical channels in steady-state, Metaheuristics in combinatorial optimization

Cites Work