본문 바로가기

전체 글

 (132)
NP hard 문제에 대한 접근법 대부분의 discrete optimization problem 은 NP-hard 이다. 만일 P!=NP 일 경우에 우리는 NP-hard 문제를 (1) 다항 시간 내에 (2) 모든 인스턴스(예제 문제)에 대해서 (3) 최적값을 구할 수 있는 알고리즘을 찾아낼 수 없을 것이다. 그래서 연구자들이 택하는 접근법은 종종 세가지 조건중 하나를 완화하여 접근한다. 첫째로 다항 시간 조건을 완화한다면 어떻게 최적해를 더 효율적으로 탐색해나갈지 고민하는것에 집중해볼 수 있다. 하지만 이 경우 어떤 인스에 대해 수 분에서 수십 시간 안에 최적해를 구해내는데 성공했다 할지라도 바로 다음 예제의 최적해를 합리적 시간안에 구해낼 것이라 장점할 수 없는 것이 가장 큰 문제이다. 두번째로 모든 instance 에 대해 일반적으로..
[Gurobi] big-M constraint 가 일으킬 수 있는 문제 big-M constraint 은 gurobi 를 포함한 많은 최적화 솔버에서 해의 불안정성 (instability) 문제를 일으킨다. 우선 아래 예시를 통해 big-M constraint 가 무엇인지부터 살펴보자. y는 도로를 사용할지 말지 결정하는 binary variable 이고 10^6은 도로의 용량을 나타내며 x는 차량의 통행량이라고 해보자. 첫번째 수식을 살펴보면 y=0이면 x
교통분야 학회 목록 IEEE ITSC https://its.papercept.net/conferences/scripts/start.pl/ Start Page of the Conference Management System The IEEE Intelligent Transportation Systems Society Conference Management System its.papercept.net ICCPS https://www.google.com/search?q=ICCPS&client=safari&source=hp&ei=geqLYajVFdXY1sQP5oergAM&iflsig=ALs-wAMAAAAAYYv4kWT-mGmbkJJPqRMs0B520Vm8UUSv&oq=ICCPS&gs_lcp=Cgdnd3Mtd2l6EAMyBQgAEIA..
ILP 문제를 푸는 exact method (cutting plane, branch-and-bound, branch-and-cut) ILP in practice ILP는 np hard 이기 때문에 이론적으로 optimal solution 을 구할 수 있을 것이라 기대할 수 없다. 하지만 현실에서 많은 경우 ILP 솔버가 최적해를 준다. 이는 ILP 의 정확해를 찾아주는 Exact algorithm 이 많이 발전했기 때문이다. 아주 나이브하게 생각해보면 ILP 를 풀기 위한 첫걸음으로 LP relaxation 을 생각해볼 수 있다. 쉽게말해 변수가 integer 라는 제약만 없애고 LP 문제를 푸는것이다. 당연히 얻은 결과는 정수가 아니라 실수일 수 있다. 이를 정수해로 변환하기 위해 반올림을 하면 어떨까? 이렇게 구한 해는 최적해가 아닐 수 있을 뿐더러 심지어는 feasible 한 해가 아닐 수도 있다. 우리에게는 반올림 보다는 조금..
[영어미팅] 줌 미팅중 먼저 나갈때 채팅창에 쓸수있는 말 줌미팅중 먼저 나가야할때가 종종 있다. 첨엔 뭐라고 말할지 몰라서 사람들은 어떻게하나 관찰했는데 다들 채팅창에 아래 중 하나를 투척하고 나감. 다들 많이 쓰는말들만 복사해놨당 I have to run; thank you! GTG(got to go의 줄임말). Thanks all! Have to head off to another meeting — thanks! Hi All - I need to drop off to deal with something right now. See you all next week.
c++ library 설치하기 c++의 다음 커멘드는 python 의 import library 에 대응된다. #include #include "fusion.h" 다음과 같은 에러메세지가 뜬다면 실제로 라이브러리를 다운로드해주는 과정이 필요한것이다 (파이썬에서 pip install) fatal error: 'boost/algorithm/string.hpp' file not found fatal error: 'fusion.h' file not found 다음 사이트에서 brew 를 다운로드한다. 홈페이지에 나와있는 커멘드 라인을 복사해다가 커멘드라인에 붙여넣기만 하면 된다. https://brew.sh Homebrew The Missing Package Manager for macOS (or Linux). brew.sh
TSP 연구에 사용할만한 솔버와 예제 문제 TSP란? TSP 는 np hard 문제이다. 다항 시간 내에 최적해를 찾을 수 없는 문제의 특성때문에 사이즈가 큰 instance 의 경우 아직도 최적해를 찾아나가고 있는 중이며 현재까지 찾은 해중 가장 좋은 해를 best known solution 이라 명명한다 TSPLIB 유명한 instance 들은 아래에서 찾아볼 수 있다. 만일 누군가 TSP 문제를 더 효율적으로 풀기 위한 heuristic 을 개발했다고 해보자. 그 성능 (얼마나 빨리 더 좋은 해를 찾나) 을 기존에 제시된 알고리즘과 비교하기위해 특수한 instance 가 아니라 잘 알려진 instance 에 적용해보고 싶을 수 있다. 그럴때 사용할수 있는 것이 TSPLIB 이다. http://comopt.ifi.uni-heidelberg.d..
서버 사용을 위한 환경 구축하기 1. 에디터 사용하기 파일 수정 및 관리를 위해서 사용하는 에디터로는 vim, emacs 가 가장 유명하다. 몇몇 사람들은 기능이 더 풍부하다는 이유로 emacs를 선호하기도 하지만 내 관점에서는 vim 으로 충분해보인다. 간단한 작업만을 할 계획이라면 nano가 초보자가 사용하기 가장 편리하다. vim filename 이라 치면 filename 이라는 파일을 생성하거나 (이미 해당 이름의 파일이 있는경우) 파일을 수정할 수 있다. view filename 이라고 치면 읽기 전용으로 파일을 열 수 있다. 더욱 편리한 사용성을 위해 vim 에디터를 개인 선호에 맞춰 커스터마이징 할 수도 있다. 홈 디렉토리 (cd ~ 를 입력하면 홈 디렉토리로 이동한다)에 .vimrc라는 이름의 히든 파일을 생성하고 (명령..

티스토리툴바