Variable Ordering Algorithms Using Problem Classifying Rule

손석원

Journal of The Korea Society of Computer and Information

Abbr : JKSCI
2011, 16(4), pp.129-138
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science

손석원 ¹

¹ 호서대학교

ABSTRACT

Efficient ordering of decision variables is one of the methods that find solutions quickly in the depth first search using backtracking. At this time, development of variables ordering algorithms considering dynamic and static properties of the problems is very important. However, to exploit optimal variable ordering algorithms appropriate to the problems. In this paper, we propose a problem classifying rule which provides problem type based on variables' properties, and use this rule to predict optimal type of variable ordering algorithms. We choose frequency allocation problem as a DS-type whose decision variables have dynamic and static properties, and estimate optimal variable ordering algorithm. We also show the usefulness of problem classifying rule by applying base station problem as a special case whose problem type is not generated from the presented rule.
KEYWORDS

Variable Ordering , Backtracking Search , Problem Classifying Rule
REFERENCES (26)

[journal] Tunchan Cura / 2010 / A parallel local search approach to solving the uncapacitated warehouse location problem / Computers & Industrial Engineering 59 (4) : 1000~1009

[confproc] C. Frei / 1999 / Resource allocation in networks using abstraction and constraint satisfaction techniques / in 5th International Conference on Principles and Practice of Constraint Programming (CP'99), Lecture Notes in Computer Science : 204~218

[journal] P. van Leeuwen / 2002 / Scheduling aircraft using constraint satisfaction / Electronic Notes in Theoretical Computer Science 76

[journal] M. Caramia / 2002 / Constraint propagation in graph coloring / Journal of Heuristics 8 (1) : 83~107

[journal] J.-F. Puget / 1998 / A constraint satisfaction approach to a circuit design problem / Journal of Global Optimization 13 (1) : 75~93

[book] Francesca Rossi / 2008 / Preferences in Constraint Satisfaction and Optimization / AI magazine : 58~68

[confproc] P. San Segundo / 2009 / Using Graphs to Derive CSP Heuristics and its Application to Sudoku / 21st International Conference on Tools with Artificial Intelligence : 538~545

[book] H. Hoos / 2004 / Stochastic Local Search : Foundations and Applications / Morgan Kaufmann

[confproc] Jia-Hong Wu / 2008 / Stochastic Enforced Hill-Climbing / Proceedings of the 18th International Conference on Automated Planning and Scheduling : 396~403

[confproc] Bruce Hajek / 1985 / A tutorial survey of theory and applications of simulated annealing / 24th IEEE Conference on Decision and Control : 755~760

[journal] L. Michel / 2004 / A simple tabu search for warehouse location / European Journal on Operations Research 157 (3) : 576~591

[confproc] S. Prestwich / 2001 / Local search and backtracking vs non-systematic backtracking / In AAAI 2001 Fall Symposium on Using Uncertainty within Computation

[book] B. M. Smith / 1996 / Succeed-first or fail-first: A case study in variable and value ordering / University of Leeds

[confproc] I. P. Gent / 1996 / An empirical study of dynamic variable ordering heuristics for the constraint satisfaction problem / in Principles and Practice of Constraint Programming : 179~193

[journal] R. M. Haralick / 1980 / Increasing tree search efficiency for constraint satisfaction problems / Artificial Intelligence 14 (3) : 263~313

[journal] E. C. Freuder / 1982 / A sufficient condition for backtrack-free search / Journal of ACM 29 (1) : 24~32

[journal] D. Brelaz / 1979 / New methods to color the vertices of a graph / Communication of the ACM 22 (4) : 251~256

[journal] B. M. Smith / 1999 / The Brelaz heuristic and optimal static orderings / in CP series, Lecture Notes in Computer Science 1713 : 405~418

[journal] C. Bessiere / 1996 / MAC and combined heuristics: Two reasons to forsake FC (and CBJ?) on hard problems / in CP series. Lecture Notes in Computer Science 1118 : 61~75

[journal] B. Hnich / 2004 / Dual modelling of permutation and injection problems / Journal of Artificial Intelligence Ressearch 21 : 357~391

[book] DY Kim / 2002 / Research on Legal System for Vitalizations of Low Power Radio Broadcasting / Korea Information Society Development Institute

[journal] E. Amaldi / 2003 / Planning UMTS Base Station Location: Optimization Models with Power Control and Algorithms / IEEE Trans. on Wireless Communications 2 (5) : 939~952

[confproc] S.A. Ali / 2002 / A Set Partitioning Approach for Cellular Planning of Mobile Radio Network / IEEE Int'l Conference on Communications : 1028~1032

[book] R. Mathar / 2001 / Optimal Base Station Positioning and Channel Assignment for 3G Mobile Networks by Integer Programming / Annals of Operations Research : 225~236

[journal] 이관형 / 2006 / On the Performance of Multicarrier CDMA Systems in Multipath Fading Channel / 한국컴퓨터정보학회논문지 / 한국컴퓨터정보학회 11 (3) : 271~280

[journal] R.Yates / 1995 / Integrated Power Control Cand base Station Assignment / IEEE Transactions on Vehicular Technology 44 : 638~644
KCI Citation (1)

KJC Korea
Journal Central

Statistics

Tools