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 126
- Downloads 0
Drag and Drop: Influences on the Design of Reusable Software Components
The fundamental unit of large scale software construction is he component. A component is the fundamental user interface object in Java. Everything you see on the display in a java pplication is a component. The abilit...
Algorithm for Solving Job Shop Scheduling Problem Based on machine availability constraint
Typically, general job shop scheduling problems assume that working times of machines are equal, for instance eight hours a day. However, in real factories, these working times are different because the machines may have...
Improved Hybrid Clustering and Distance-based Technique for Outlier Removal
Outliers detection is a task that finds objects that are dissimilar or inconsistent with respect to the remaining data. It has many uses in applications like fraud detection, network intrusion detection and clinical diag...
A Novel Algorithm for Scaling up the Accuracy of Decision Trees
Classification is one of the most efficient and widely used data mining technique. In classification, Decision trees can handle high dimensional data, and their representation is intuitive and generally easy to assimilat...
Development of Coalmine Safety System Using Wireless Sensor Network
In the Era of embedded technology, the Zigbee protocols are used in more and more applications. Because of the rapid development of sensors, microcontrollers, and network technology, a reliable technological condition ha...