A Backtracking Search Framework for Constraint Satisfaction Optimization Problems


The KIPS Transactions:PartA, Vol. 18, No. 3, pp. 115-122, Jun. 2011
10.3745/KIPSTA.2011.18.3.115,   PDF Download:

Abstract

It is very hard to obtain a general algorithm for solution of all the constraint satisfaction optimization problems. However, if the whole problem is separated into subproblems by characteristics of decision variables, we can assume that an algorithm to obtain solutions of these subproblems is easier. Under the assumption, we propose a problem classifying rule which subdivide the whole problem, and develop backtracking algorithms fit for these subproblems. One of the methods of finding a quick solution is efficiently arrange for any order of the search tree nodes. We choose the cluster head positioning problem in wireless sensor networks in which static characteristics is dominant and interference minimization problem of RFID readers that has hybrid mixture of static and dynamic characteristics. For these problems, we develop optimal variable ordering algorithms, and compare with the conventional methods. As a result of classifying the problem into subproblems, we can realize a backtracking framework for systematic search. We also have shown that developed backtracking algorithms have good performance in their quality.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
S. W. Sohn, "A Backtracking Search Framework for Constraint Satisfaction Optimization Problems," The KIPS Transactions:PartA, vol. 18, no. 3, pp. 115-122, 2011. DOI: 10.3745/KIPSTA.2011.18.3.115.

[ACM Style]
Surg Won Sohn. 2011. A Backtracking Search Framework for Constraint Satisfaction Optimization Problems. The KIPS Transactions:PartA, 18, 3, (2011), 115-122. DOI: 10.3745/KIPSTA.2011.18.3.115.