석박사/최적화는 사기가 아니얏! (11) 썸네일형 리스트형 TSP 연구에 사용할만한 솔버와 예제 문제 TSP란? TSP 는 np hard 문제이다. 다항 시간 내에 최적해를 찾을 수 없는 문제의 특성때문에 사이즈가 큰 instance 의 경우 아직도 최적해를 찾아나가고 있는 중이며 현재까지 찾은 해중 가장 좋은 해를 best known solution 이라 명명한다 TSPLIB 유명한 instance 들은 아래에서 찾아볼 수 있다. 만일 누군가 TSP 문제를 더 효율적으로 풀기 위한 heuristic 을 개발했다고 해보자. 그 성능 (얼마나 빨리 더 좋은 해를 찾나) 을 기존에 제시된 알고리즘과 비교하기위해 특수한 instance 가 아니라 잘 알려진 instance 에 적용해보고 싶을 수 있다. 그럴때 사용할수 있는 것이 TSPLIB 이다. http://comopt.ifi.uni-heidelberg.d.. [최적화 솔버] Google ortools 와 GUROBI index.php/en/ https://w1.cirrelt.ca/~vidalt/en/VRP-resources.html 기존에 최적화 문제를 풀기 위해서 ortools 를 많이 써왔었는데 GUROBI 라는 최적화 솔버를 발견했다. 현존하는 솔버중에 가장 성능이 좋다고 평가되며 당연히 open source인 ortools 보다 성능이 뛰어나다. 튜토리얼도 상세하고 예제 코드도 많아 google ortools 를 이용할 정도의 실력이라면 무리 없이 사용할 수 있다. 학생이라면 아카데믹 라이센스를 신청해서 무료로 사용할 수 있다. https://www.gurobi.com/resource/modeling-examples-using-the-gurobi-python-api-in-jupyter-notebook/ Gur.. Benders decomposition https://en.wikipedia.org/wiki/Benders_decomposition Benders decomposition - Wikipedia From Wikipedia, the free encyclopedia Jump to navigation Jump to search Benders decomposition (or Benders' decomposition) is a technique in mathematical programming that allows the solution of very large linear programming problems that have a special bloc en.wikipedia.org 연구실 친구가 쓴 위키피디아 글인데 공부할 겸 일부 번역해서 정리하고.. 이전 1 2 다음
