Posts match “ optimization ” tag:

This is a paper study note for my startup travel service called StyleTrip.
The paper is Trip-Mine: An Efficient Trip Planning Approach with Travel Time Constraints

Introduction

  • How to efficiently search for the most interesting trip which satisfies a travel time constraint from a large number of attractions.
  • The efficient of trip planning is sensitive to the scalability of travel regions.
  • The optimal trip finding problem is different from Traveling Sales Problem(TSP).
  • The reason is that TSP finds the shortest path from the extra N given locations. However, the optimal trip problem is to finds a sub-permutation of given N locations.
  • The dynamic programming searches all possible trips based on the concept of DFS.

Optimization mechanisms

  • Attraction sorting ( User favorite, the must-go / popular / high-rating places )
  • Low bound checking ( meeting time, cost constaints )
  • Score Checking ( meeting low bound checking and the score is maximum)

Definitions

  • Score: It can refer to user favorite , popularity or rating value.
  • Valid trip: A trip is valid if the total trip time is less than or equal to the required travel time.
  • Optima trip: A valid trip is optimal if the Score(tripA) is maximum among the valid trip.

Proposed theorem

  • We can find out that calculation of the trip takes an exponential time, so that it can conclude that this is a NP complete problem.
  • Triangle inequality Travel time (x,y)+(y,x) >= (x,z)
  • If travel time (a0,trip1) <= (a0,trip2), then trip1 is the sub-trip of trip2.
  • Given a invalid (total trip time exploded) trip1, then any super-trip of trip1 is invalid, too. (pruning strategy 1)

Pruning strategy

  1. Given a invalid (total trip time exploded) trip1, then any super-trip of trip1 is invalid, too. Based on the pruning strategy 1, we can prune the trips which contain any invalid trip to reduce the calculations.
  2. Given an place set A, A is not a valid trip set if the trip time is greater than the travel time constraint.

Approach

  1. Find the candidate place set: starting from 1-place-set, 2-place-set (#2 permutation) ... , n-place-set (#n combination), we find all valid trip permutation and remove all the invalid trip and its super-trip permuation (pruning strategy 1).
  2. Filter the valie trip set with pruning strategy 2.
  3. The trip scores of a trip set and its all permutations are the same, so we don't need to check the permutations which satisifies the travel time constraint.

This is my note for Discrete Optimization in Coursera (https://class.coursera.org/optimization-002)


Greedy Algorithm Intuition

What is Greedy? Build a solution by picking itmes one at a time in greedy fasion.

Idea 1: more items are best.

Start with small ones and take as many as you can.

Idea 2: valuable items are best.

Start with the most valuable items.

Idea 3: value density!

Calculate dollars per kilogram.


Greedy Algorithm

  • For one problem, there are many possible greddy algorithms. Some will do better than others. (Take a look at above ideas)
  • Idea: Take the most valuable items first. And the next valuable item that can fit into a knapsack.
  • Advantages:
    1. Quick to design and implement the algorithm.
    2. It can be very fast to model the problem.
  • Problems:
    1. No quality guarantees (in general). You don't know much you can improve the algorithm, you don't know how good they are.
    2. Quality can vary widely on the input.

Summary of Greedy Algorithm:

Try to understand what the problem is. Get a base line, that's what you have to improve and then afterwards you going to use some of the techniques that we will present:

  • Constraint Programming
  • Local Searching
  • Mixed Integer Programming To improve the greedy algorithm and find out how much you can improve.

Modeling

How to formalize an optimization task as a mathematical model. This is the key to solve the optimal problem.

How to model an optimization problem

  1. Describe the problem
  2. Choose some decision variables
  3. Express the problem constraints in term of there variables
  4. Express the objective function ( the quality of the solution )
  5. There may be many ways to model an optimization problem.

Modeling the knapsack problem

  1. Describe the problem:
    • For each i in Item, has weight Wi and value Vi.
    • We have a knapsack which capacity is K.
    • We have to find the subset of Item which value is maximum and summation of weight is less than or equal to K.
  2. Choose some decision variables:
    • Xi is item i is selected or not
  3. Express the problem constraints in term of there variables:
  4. Express the objective function ( the quality of the solution ) is maximum and be subject to
  5. There may be many ways to model an optimization problem.

Dynamic Programming

Basic Principle:

  • divide and conquer
  • bottom up computation

Define the problem:

  • Item selection I = { 1, 2, 3 ...... n }
  • O( k, j ) is the optimal solution of capacity K of Item[ 1 ... j ] s.t.

maximize

and subject to

Recurrence relation

  • Before we want to solve O( k, j ), we solve sub-problemO( k, j - 1 ) first.
    O( k, j ) = max( O( k, j - 1 ), O( k - Wj, j - 1 ) + Vj ) if Wj <= K    // 第一個是不拿j, 第二個是拿j
    O( k, j ) = O( k, j - 1 ) if Wj > K  // 超重不拿j
    O( k, 0 ) = 0   // 什麼都不拿,價值就為零。
    

一、 Describe the problem

系統目標

為使用者告訴我們想去哪裡,系統告訴他一套完整行程怎麼玩。

  • 輸入: 使用者輸入地點關鍵字(想去的地方),和去的日期(何時去,選填)
  • 輸出: 引擎計算出搜尋結果的地點子集合,且該子集合為有順序性,同時滿足下列條件:
    1. 包含想去的區域內最熱門、必去的景點集合
    2. 子集合內的景點都是使用者最有興趣的
    3. 所有要去的地點花費總時間滿足時間限制
    4. 所有要去的地點在要去的期間內都有開放或營業
    5. 三餐有建議的餐飲,晚上有住宿
    6. 交通總時間要最小

Symbolization

  • For each place p in {PLACE}, has search rank R,place category pc, place weight pw , popularity & rating pr, open day 'od', open time ot, routing time rt, and spend time st.
  • For the user u, has place keywords keywords, travel dates dates (total days=D) and user favorite uf.
  • We have to find the subset trip of {PLACE}, which search rank, popularity, user favorite is maximum, the summation of routing time + spend time is less than and equal to D.

二、 Choose some decision variables

Xi 表示地點p 有選擇或沒有選擇到排程當中。

三、 Express the problem constraints in term of there variables

  1. 所有要去的地點花費總時間滿足時間限制
  2. 所有要去的地點在要去的期間內都有開放或營業
  3. 三餐有建議的餐飲,晚上有住宿

四、 Express the objective function ( the quality of the solution )

  1. 包含想去的區域內最熱門、必去的景點集合
  2. 子集合內的景點都是使用者最有興趣的
  3. 整個交通時間要最小