일기 (17) 썸네일형 리스트형 NP hard 문제에 대한 접근법 대부분의 discrete optimization problem 은 NP-hard 이다. 만일 P!=NP 일 경우에 우리는 NP-hard 문제를 (1) 다항 시간 내에 (2) 모든 인스턴스(예제 문제)에 대해서 (3) 최적값을 구할 수 있는 알고리즘을 찾아낼 수 없을 것이다. 그래서 연구자들이 택하는 접근법은 종종 세가지 조건중 하나를 완화하여 접근한다. 첫째로 다항 시간 조건을 완화한다면 어떻게 최적해를 더 효율적으로 탐색해나갈지 고민하는것에 집중해볼 수 있다. 하지만 이 경우 어떤 인스에 대해 수 분에서 수십 시간 안에 최적해를 구해내는데 성공했다 할지라도 바로 다음 예제의 최적해를 합리적 시간안에 구해낼 것이라 장점할 수 없는 것이 가장 큰 문제이다. 두번째로 모든 instance 에 대해 일반적으로.. [프라이싱] 독일의 철도카드 사례에서 본 교통 수단 가격 결정 헤르만 지몬의 프라이싱을 읽다가 교통 수단 가격 결정 문제에서 생각 해볼만한 실제 사례가 있어서 가져와보았다. 90년대 초반 독일 대다수 사람들은 철도를 기피하고 자가용을 이용했는데 주된 이유는 가격이었다. 철도 기차 요금이 자가용 연료 비용보다 두배가량 비쌌기 때문이었다. 교통 분야의 선행 연구를 살펴보면 통행자들이 철도와 자가용 사이에 수단 선택을 할때 자가용 비용은 당장 주머니에서 빠져나가는 돈인 연료 비용만 고려한다는 연구 결과가 많다. 실제로 자가용을 이용할때는 보험료, 감가상각 등 고정비용이 들지만 일 단위 수단 선택을 할 때에는 그것을 인지하기 어렵다는 것이다. 독일의 철도 회사는 바로 이 점에 착안해서 기차 요금도 변동비와 고정비로 구분할 방법을 찾아낸다. 철도 카드 50을 만든 것이다. .. Palm Khintchine Theorem - 포아송 분포 시간대별 공공자전거 대여소의 대여/반납 이용 수요를 포아송 분포로 가정할 수 있는 이유 아래와 같은 reasoning 을 따라가보자. Palm Khintchine Theorem 의 핵심 아이디어를 따른다. n 명의 사람들이 각기 독립적으로 행동하는 상황을 생각해보자. 시간을 한 유닛 단위 (델타) 로 나눴다고 생각해보자 -이를 보통 영어로는 time slot이라 표현한다-. 어떤 이벤트의 발생 확률은 람다 라고 가정해보자. 각 사람이 한 time slot 안에 특정 이벤트를 발생시킬 확률은 다음과 같이 표현한다. $$p_n = \lambda \delta/n$$ 이제 한 time slot안에 어떤 이벤트의 총 발생 횟수는 이항 확률 분포를 따른다고 할 수 있다. $$Bionomial(n, p_n)$$ n이.. 공공자전거 최적화 문제로 포뮬레이션하기 보통 공공자전거 문제를 최적화 문제로 풀면 목적 함수가 maximize customer satisfaction/revenue 혹은 minimize outages (자전거를 대여하고자 할때 재고 없는 상황/반납하고자 할때 반납가능한 거치대 (dock/rack) 이 없는 상황) 될 것이라고 쉽게 생각할 수 있다. 한가지 중요한것은 사람들이 대여/반납할 때 실패하는 상황은 데이터에 드러나지 않는다는 것이다. 이 현상을 censoring 이라 한다. 최적화 문제에서의 결정 변수(decision variables)를 다음과 같이 설정할 수 있다. Station locations: (every year)Station capacity: (every 6 months)Number of bikes at each stati.. Transportation Research Board (TRB) 99th Annual Meeting 참관기 ~~ 지난해 제가 도로 학회지에 제출했던 컨퍼런스 참관기입니다.~~ 매년 워싱턴에서 개최되는 Transportation Research Board (TRB) Annual Meeting은 제출 논문의 절반 이상이 발표 불가가 된다고 알려진 국제학술대회이다. 따라서 TRB Annual Meeting에서의 발표는 아직 석사과정을 밟고 있는 나로서 쉽지 않았던 도전인 동시에 졸업 전 이루고 싶은 목표 중 하나였다. 국내에서는 이미 ITS와 대한교통학회에 참석하여 발표한 경험이 있지만, 해외 학회 참석은 처음이었고 이번 경험 은 나에게 진정한 학술대회의 의미를 깨닫게 해 주었다. TRB Annual Meeting은 교통 분야 최대 규모 학회라는 명성에 걸맞게 한국을 넘어 전 세계 교통인과 교류할 수 있는 만남의 .. 맥 포트불량 io보드 교체 후기 (가로수길 애플 서비스 센터, 애플렌탈) 맥 포트 2개 중 하나가 충전조차 되지 않고 그나마 충전이 잘되는 하나는 usb, 모니터 등 여러 장치를 연결해서 (전압이 많이 가해지면) 간헐적으로 연결이 끊어지는 현상이 일어났다. 맥 수리를 위해서는 애플 지원 앱을 깔아야한다. 지원 앱을 통해 서비스 센터를 예약할 수 있는데 나는 강남역 부근 서비스 센터와 가로수길 센터를 방문해봤다. 강남역 부근 서비스 센터에 방문했을때 2~3주 정도 시간이 걸릴 수도 있다는 얘기를 듣고 학기중이라 불가능하겠다고 판단하고 학기가 끝난 이후에 가로수길 센터를 찾았다. 타임머신 앱으로 미리 백업을 진행했다. 우선 가로수길 센터로 방문하길 잘했다는 생각이 들었던게, 훨씬 전문적이었다. 강남역 부근 서비스 센터에서는 원인 파악해주는 과정이 없고 무조건 맡겨야하는데 가로수길.. Unconstrained optimization, Gradient Descent [읽기 전에.. ] 1. 용어정리 minimum, minimizer : 최소값, 최소점 2. 선수학습 Taylor series expansion 관련 내용이 종종 나오므로 간단한 개념을 알아야 잘 이해할 수 있다. 3. 관련 포스팅 예전 글에서 gradient descent 에 대해 정리한 적 있다. 그때 글은 gradient descent 를 한번에 이해할 수 있도록 돕기 위해 우리가 한번쯤 접해봤을 법 한 _선형회귀 함수를 fitting 하는 과정_을 gradient descent 를 이용해서 어떻게 하는지를 단적인 예시로 보여주었다면, 이번 글은 조금 더 큰 맥락에서의 설명이 될 것이다. youngseokim.tistory.com/81?category=911369 Stochastic Gradient.. Simplex method 에서 basis 를 나간 basic variable은 바로 다음 pivot 에 들어올 수 있을까? Q1. Simplex method 에서 특정 pivot 에서 basis 를 나간 어떤 basic variable x_j는 그 바로 다음 pivot 에서 들어올 수 있을까? 없다. 기하학적으로 생각해보자. 특정 pivot 과 그 다음 pivot 의 basis 는 adjacent basic feasible solution 이다. 즉, 하나만 빼고 모두 같은 basic variable 을 공유한다. extreme points 들이 다면체의 꼭지점들이라고 본다면 한 꼭지점에서 (BFS) iteration 이 끝나면 다른 인접한 꼭지점으로 edge를 따라 이동해서 다른 꼭지점 (adjacent BFS)에 도달하는 셈이다. 이러한 관점에서 봤을때 특정 basis 를 나간 어떤 basic variable x가 바로 .. 이전 1 2 3 다음
