일기 (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.. 이전 1 2 3 4 5 다음