A hybrid soft computing approach for subset problems

DOI10.1155/2013/716069MaRDI QIDQ474017zbMATH OpenOpenAlexWikidataFDO

Authors Broderick Crawford, Ricardo L. Soto, Eric Monfroy, C. Castro, Wenceslao Palma, Fernando Paredes

Publication date 24 November 2014

Published in Mathematical Problems in Engineering (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1155/2013/716069

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Review text

Summary: Subset problems (set partitioning, packing, and covering) are formal models for many practical optimization problems. A set partitioning problem determines how the items in one set can be partitioned into smaller subsets. All items in the set must be contained in one and only one partition. Related problems are set packing (all items must be contained in zero or one partitions) and set covering (all items must be contained in at least one partition). Here, we present a hybrid solver based on ant colony optimization (ACO) combined with arc consistency for solving this kind of problems. ACO is a swarm intelligence metaheuristic inspired on ants behavior when they search for food. It allows to solve complex combinatorial problems for which traditional mathematical techniques may fail. By other side, in constraint programming, the solving process of Constraint Satisfaction Problems can dramatically reduce the search space by means of arc consistency enforcing constraint consistencies either prior to or during search. Our hybrid approach was tested with set covering and set partitioning dataset benchmarks. It was observed that the performance of ACO had been improved embedding this filtering technique in its constructive phase.

Recommendations

• VERY STRONGLY CONSTRAINED PROBLEMS: AN ANT COLONY OPTIMIZATION APPROACH
• Application of ant colony optimization metaheuristic on set covering problems
• Sensitivity analysis of ACO start strategies for subset problems
• scientific article; zbMATH DE number 1594538
• Start Strategies of ACO Applied on Subset Problems

Cites work

• A probabilistic heuristic for a computationally difficult set covering problem
• A Set Partitioning Approach to the Crew Scheduling Problem
• A Set-Partitioning-Based Heuristic for the Vehicle Routing Problem
• Backjump-based backtracking for constraint satisfaction problems
• Consistency in networks of relations
• Constraint handling in genetic algorithms: the set partitioning problem
• On some difficult linear programs coming from set partitioning
• Set partitioning/covering-based approaches for the integrated vehicle and crew scheduling problem
• VERY STRONGLY CONSTRAINED PROBLEMS: AN ANT COLONY OPTIMIZATION APPROACH

Cited in

(4)

• A bicriteria approach identifying nondominated portfolios
• Catfish bat algorithm-ant colony optimization for subset problems
• The impact of a new formulation when solving the set covering problem using the ACO metaheuristic
• A depth-based heuristic to solve the multi-objective influence spread problem using particle swarm optimization

This page was built for publication: A hybrid soft computing approach for subset problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q474017)