선형계획법 (6) 썸네일형 리스트형 설비 입지 선정 원-쌍대 근사 알고리즘 (Primal-Dual Approximation Algorithm for Facility Location) 지난 포스트에서 우리는 설비 후보지들이 주어질 때 최소의 비용으로 몇 곳의 후보지에 설비를 지어 모든 고객을 서비스하는 방법을 찾는 설비 입지 선정 문제(facility location problem)를 공부하였습니다. 언뜻 보기에도 산업적으로 유용해 보이는 이 문제는 이론적으로도 흥미로운 부분이 많아서 널리 연구가 되었습니다. 지난 포스트에서는 그중에서도 특히 이 문제를 해결하는 4-근사 알고리즘을 배웠습니다. 설비 입지 선정 문제 (Facility Location Problem) 여러분이 큰 물류 회사를 경영한다고 가정해 봅시다. 여러분에게는 수많은 고객들이 있으며 여러분은 그들에게 상품을 배송해 주어야 합니다. 이를 위해서는 몇몇 장소에 큰 물류 창고를 건설 gazelle-and-cs.tistory.. 설비 입지 선정 문제 (Facility Location Problem) 여러분이 큰 물류 회사를 경영한다고 가정해 봅시다. 여러분에게는 수많은 고객들이 있으며 여러분은 그들에게 상품을 배송해 주어야 합니다. 이를 위해서는 몇몇 장소에 큰 물류 창고를 건설해야 하겠죠. 여러 곳에서 자문을 얻어 물류 창고를 건설할 후보지를 받아 놓았다고 합시다. 이제 여러분은 큰 결단의 기로에 서게 됩니다. 바로 후보지 중 어느 곳에 물류 창고를 건설할지 결정해야 합니다. 고려해야 하는 요인은 크게 두 가지입니다. 하나는 각 후보지마다 물류 창고를 건설하게 될 때 발생할 비용일 것이고, 다른 하나는 물류 창고에서 각 고객에게 상품을 배송할 때 들어가는 비용입니다. 경영자의 입장에서 여러분은 당연히 총 비용이 최소가 되도록 하고 싶습니다. 과연 어느 후보지에 물류 창고를 건설하면 될까요? 실제 .. 파이썬 PuLP 입문 제가 주로 하는 연구가 조합론적 최적화 쪽이다 보니 아무래도 선형 계획법(linear programming, LP)을 풀어야 할 때가 적잖이 있습니다. 그럴 때마다 예전에는 CPLEX나 Gurobi와 같은 프로그램을 C++로 불러서 해결을 했었습니다. 그렇지만 이를 사용하려면 여러 설정을 만져 줘야하는 번거로움이 있었습니다. 또, C++ 자체가 아무래도 오래된 언어다 보니 문자열 처리 등 개인적으로 불편한 부분도 많았죠.(이를 연구실 동료가 들으면 기겁하겠지만요. 하하.) 마지막으로 CPLEX나 Gurobi 모두, 비록 학술용 라이센스를 제공하기는 하지만, 상용 소프트웨어라는 점도 마음에 걸렸습니다. 그러던 와중에 파이썬에서 LP를 해결해 주는 오픈 소스 라이브러리가 있다는 것을 최근 알게 되었습니다. .. 검색 엔진 회사가 검색어로 수익을 내는 방법 (Ad-Auctions Problem) 물론 그 외에도 다양한 방안이 있겠지만, 다음이나 네이버와 같은 검색 엔진(search engine) 회사들이 수익을 내는 가장 기본적인 방법은 광고입니다. 하지만 이들의 광고 방식은 정해진 지면에 싣거나 정해진 시간에 방송하는 전통적인 광고와는 다른 점이 있죠. 바로 각 사용자의 정보를 알고 이를 토대로 각각에게 알맞는 광고를 보여줄 수 있다는 것입니다. 이들이 활용할 수 있는 정보는 매우 다양하지만, 그 중에서도 검색 엔진 회사가 가장 쉽게 이용할 수 있는 것은 사용자의 검색어입니다. 사용자가 어떤 특정한 검색어를 입력하면, 해당 검색어에 알맞는 광고를 보여주는 것이죠. 여러분들도 검색 엔진에서 무언가를 찾을 때 이와 연관된 광고가 결과 페이지에 함께 나타나는 것을 본 경험이 있을 것입니다. 회사마다.. [스키 대여 문제 / Ski Rental Problem] 선형 계획법을 이용한 Randomized Algorithm 스키 대여 문제(ski rental problem)에 대해서 잘 모르시는 분들은 이 글을 읽기 전에 이전 포스트를 읽어 보시는 것을 추천드립니다. 2020/03/15 - [온라인 알고리즘/Ski rental problem] - [스키 대여 문제 / Ski rental problem] 문제 정의 & break-even algorithm [스키 대여 문제 / Ski rental problem] 문제 정의 & break-even algorithm 이번 포스트에서는 기초적인 온라인 문제 중 하나인 스키 대여 문제(ski rental problem)를 다루어 보도록 하겠습니다. 온라인 문제 및 온라인 알고리즘이 무엇인지는 이전 글을 참조해 주시기 바랍니다. 아래의.. gazelle-and-cs.tistory.co.. [선형 계획법] 쌍대성(Duality) Linear programming은 최적화 분야에서 잘 알려지고 연구되었으며 실제로도 많이 응용되는 기법입니다. 줄여서 LP라고도 하며, 우리말로는 선형계획법으로 불립니다. 이름이 뭔가 멋들어져서 괜스레 어렵게 느껴질 수도 있겠습니다만, 사실 별것 아닙니다. 고등학교 수학 시간에 다음과 같은 문제를 풀어보신 적이 있을 겁니다. 여러분은 빵집 사장님입니다. 식빵과 크루아상, 두 종류의 빵을 팔고 있습니다. 식빵 1kg을 만들기 위해서는 밀가루 5kg, 설탕 3kg이 필요하고 크루아상 1kg을 만들기 위해서는 밀가루 2kg, 설탕 5kg이 필요하다고 합시다. 1kg 당 식빵과 크루아상의 가격은 같습니다. (저는 제빵을 잘 모릅니다. 수치는 그저 예시일 뿐입니다.) 하루에 밀가루 20kg, 설탕 15kg이 들.. 이전 1 다음
