An Integer Programming-based Local Search for Large-scale Maximal Covering Problems
Journal Title: International Journal on Computer Science and Engineering - Year 2011, Vol 3, Issue 2
Abstract
Maximal covering problem (MCP) is classified as a linear integer optimization problem which can be effectively solved by integer programming technique. However, as the problem size grows, integer programming requires excessive time to get an optimal solution. This paper suggests a method for applying integer programming-based local search (IPbLS) to solve large-scale maximal covering problems. IPbLS, which is a hybrid technique combining integer programming and local search, is a kind of local search using integer programming for neighbor generation. IPbLS itself is very effective for MCP. In addition, we improve the performance of IPbLS for MCP through problem reduction based on the current solution. Experimental results show that the proposed method considerably outperforms any other local search techniques and integer programming.
Authors and Affiliations
Junha Hwang , Sungyoung Kim
Keywords
Related Articles
- EP ID EP155335
- DOI -
- Views 122
- Downloads 0
Comparative Study of Three Declarative Knowledge Representation Techniques
In artificial intelligence to solve the problem user require a knowledge base, consist all information related to problem domain and a method for manipulating the knowledge for finding the solution. For better result kno...
Image Compression Using Fast 2-D DCT Technique
Image Compression is a method, which reduces the size of the data to reduce the amount of space required to store the data. The Discrete cosine transform (DCT) is a method for transforms a signal or image from spatial do...
New Design Metrics for Complexity Estimation in Object Oriented Systems
This paper proposes four design metrics of class level for early and effective feedback to manage the quality of object-oriented software. These metrics measure the complexity induced by the use of various object-oriente...
A Survey on Sensor’s Drift Counteraction Using Dynamic Pattern Recognition System
In past years, numerous electronic nose (e-nose) evelopments have been published describing analyses of solid-, liquid- or gaseous media in microbiological-environmental-, gricultural- or medical applications. However, l...
A generic conceptual and UML model for the multi-echelon distribution supply chain
The Multi-Echelon Distribution Supply Chain (MEDSC) is a multifaceted structure, focusing on the integration of all factors that involved in the overall distribution process of finished products to the customers. The gro...