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 125
- Downloads 0
SEGMENTATION OF LUNG CANCER PET SCAN IMAGES USING FUZZY CMEANS
Image segmentation plays a vital role in medical image processing. Eventually, the proposed work is subjected to classify the tumour and non-tumour parts, followed by the segmentation of tumour region in PET scan images....
A New Look to Traversal Algorithms Using Set Construct Data Structure
Tree traversal refers to the process of visiting or examining or updating each node in a tree data structure, exactly once, in a systematic way. Such traversals are classified by the order in which the nodes of the tree...
Secure Mobile Agent based Information Gathering in Wireless Network
Nowadays, everything is moving towards the wireless environment to bring the smartness to the society. In this situation, it is necessary to bring the smart technologies in the wireless environment. By considering this i...
Process Mining in Dyeing Unit Using Organizational Perspective: A Case Study
The basic idea of process mining is to extract knowledge from event logs recorded by an information system. Until recently, the information in these event logs was rarely used to analyze the underlying processes. Process...
Diagnosis and Medical Prescription of Heart Disease Using Support Vector Machine and Feedforward Backpropagation technique
Expert system are used extensively in many domains. Heart disease diagnosis is a complicated process and requires high level of expertise. This paper describes aiming to develop a expert system for diagnosing of heart d...