Journal of the Korea Society of Computer and Information (한국컴퓨터정보학회논문지)

Korean Society of Computer Information (한국컴퓨터정보학회)
권호 표지
DOI QR코드

DOI QR Code

Variable Ordering Algorithms Using Problem Classifying

문제분류규칙을 이용한 변수 순서화 알고리즘

  • Received : 2010.12.06
  • Accepted : 2011.01.20
  • Published : 2011.04.30
Download PDF
⟨ Previous Next ⟩

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.

백트래킹을 이용한 깊이우선탐색에서 해를 빨리 찾기 위한 방법 중 하나는 결정변수의 순서를 효과적으로 배열하는 것이다. 이 때 문제의 동적 및 정적 특성을 고려한 변수 순서화 알고리즘 개발은 매우 중요한 문제이다. 그러나 문제에 적합한 최적의 변수 순서화 알고리즘을 개발하는 것은 어려운 문제이다. 본 논문에서는 변수의 속성에 기반을 두어 문제의 형태를 규정하는 문제분류규칙을 제안하고 이 규칙을 이용하여 문제에 적합한 변수 순서화 알고리즘의 형태를 예측할 수 있게 한다. 결정변수가 동적 및 정적 특성을 갖는 DS-type 문제로서 주파수 할당문제를 선택하여 최적의 변수 순서화 알고리즘을 예측한다. 또한 문제분류규칙에 의해 생성되지 않는 특별한 형태의 문제인 기지국 위치문제를 적용하여 제안하는 문제분류규칙의 효용성을 입증한다.

Keywords

References

  1. Tunchan Cura, "A parallel local search approach to solving the uncapacitated warehouse location problem," Computers & Industrial Engineering, Vol. 59, Issue 4, pp. 1000-1009, Nov. 2010. https://doi.org/10.1016/j.cie.2010.09.012
  2. C. Frei and B. Faltings, "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, Vol. 1713, pp. 204-218, Oct. 1999,
  3. P. van Leeuwen, H. Hesselink, and J. Rohling, "Scheduling aircraft using constraint satisfaction," Electronic Notes in Theoretical Computer Science, vol. 76, 2002.
  4. M. Caramia and P. Dell'Olmo, "Constraint propagation in graph coloring," Journal of Heuristics, vol. 8, no. 1, pp. 83-107, 2002. https://doi.org/10.1023/A:1013665718444
  5. J.-F. Puget and P. V. Hentenryck, "A constraint satisfaction approach to a circuit design problem," Journal of Global Optimization, vol. 13, no. 1, pp. 75-93, 1998. https://doi.org/10.1023/A:1008236911603
  6. Francesca Rossi, K. Brent Venable, and Toby Walsh, "Preferences in Constraint Satisfaction and Optimization," AI magazine, pp. 58-68, AAAI, 2008.
  7. P. San Segundo and A. Jimenez, "Using Graphs to Derive CSP Heuristics and its Application to Sudoku," 21st International Conference on Tools with Artificial Intelligence, pp.538-545, Nov. 2009.
  8. H. Hoos and T. Stutzle, Eds., "Stochastic Local Search : Foundations and Applications" Morgan Kaufmann, 2004.
  9. Jia-Hong Wu, Rajesh Kalyanam, and Robert Givan, "Stochastic Enforced Hill-Climbing," Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS 2008), pp. 396-403, AAAI, 2008.
  10. Bruce Hajek, "A tutorial survey of theory and applications of simulated annealing," 24th IEEE Conference on Decision and Control, vol. 24, pp.755-760, Dec. 1985.
  11. L. Michel and P. V. Hentenryck, "A simple tabu search for warehouse location," European Journal on Operations Research, vol. 157, no. 3, pp. 576- 591, 2004. https://doi.org/10.1016/S0377-2217(03)00247-9
  12. S. Prestwich, "Local search and backtracking vs non-systematic backtracking," In AAAI 2001 Fall Symposium on Using Uncertainty within Computation, 2001.
  13. B. M. Smith, "Succeed-first or fail-first: A case study in variable and value ordering," University of Leeds, U.K., Tech. Rep. 96.26, 1996.
  14. I. P. Gent, E. MacIntyre, P. Prosser, B. M. Smith, and T. Walsh, "An empirical study of dynamic variable ordering heuristics for the constraint satisfaction problem," in Principles and Practice of Constraint Programming, pp. 179-193, 1996.
  15. R. M. Haralick and G. L. Elliott, "Increasing tree search efficiency for constraint satisfaction problems," Artificial Intelligence, vol. 14, no. 3, pp. 263-313, 1980. https://doi.org/10.1016/0004-3702(80)90051-X
  16. E. C. Freuder, "A sufficient condition for backtrack-free search," Journal of ACM, vol. 29, no. 1, pp. 24-32, 1982. https://doi.org/10.1145/322290.322292
  17. D. Brelaz, "New methods to color the vertices of a graph," Communication of the ACM, vol. 22, no. 4, pp. 251-256, 1979. https://doi.org/10.1145/359094.359101
  18. B. M. Smith, "The Brelaz heuristic and optimal static orderings." in CP series, Lecture Notes in Computer Science, vol. 1713. pp. 405-418, 1999.
  19. C. Bessiere and J.-C. Regin, "MAC and combined heuristics: Two reasons to forsake FC (and CBJ?) on hard problems," in CP series. Lecture Notes in Computer Science, vol. 1118. pp. 61-75, 1996.
  20. B. Hnich, T. Walsh, and B. M. Smith, "Dual modelling of permutation and injection problems," Journal of Artificial Intelligence Ressearch, vol. 21, pp. 357-391, 2004.
  21. DY Kim, EY Han, JH Park, "Research on Legal System for Vitalizations of Low Power Radio Broadcasting" Korea Information Society Development Institute, May. 2002.
  22. E. Amaldi, A. Capone, F. Malucelli, "Planning UMTS Base Station Location: Optimization Models with Power Control and Algorithms," IEEE Trans. on Wireless Communications, Vol.2, No.5, pp.939-952, Sep. 2003. https://doi.org/10.1109/TWC.2003.817438
  23. S.A. Ali, "A Set Partitioning Approach for Cellular Planning of Mobile Radio Network," IEEE Int'l Conference on Communications," pp.1028-1032, 2002.
  24. R. Mathar, M. Schmeink, "Optimal Base Station Positioning and Channel Assignment for 3G Mobile Networks by Integer Programming," Annals of Operations Research, pp. 225-236, 2001.
  25. KH Lee and MH Lee, "On the Performance of Multicarrier CDMA Systems in Multipath Fading Channel," Journal of The Korea Society of Computer and Information, Vol. 11, No. 3, pp. 271-279, Jul. 2006.
  26. R.Yates, C.Y. Huang, "Integrated Power Control and base Station Assignment," IEEE Transactions on Vehicular Technology, Vol. 44. pp.638-644, Aug. 1995. https://doi.org/10.1109/25.406632