python の最適化ツール ortools について

# 最適化問題設定 各ユーザーにアイテムを勧めたい。条件として各ユーザーには 4 つのアイテムを勧める。各ユーザーがそのアイテムを好むかどうかはスコアとして数値化されており、選んだアイテムのスコアの合計をできるだけ大きくしたい。 ただし、アイテムはカテゴリー毎に分類されており、一つ目に勧めるアイテムが属するカテゴリー、二つ目に勧めるアイテムが属するカテゴリー、. . . 四つ目に勧めるアイテムが属するカテゴリーは決められている。 また各カテゴリーの各価格帯に対してはユーザーに勧める個数の割合が決まっており、その割合から一定の範囲に収めなければならない。 # 数式による定式化 $u = 1, \dots, U$ をユーザーを表す添字 $n = 1, \dots, N$ をレコメンドの順番を表す添字(上記の問題設定では $N=4$ ) $c = 1, \dots, C$ をカテゴリーを表す添字 $p = 1, \dots, P$ を価格帯を表す添字 とする。 - 変数 $v_{u,n,c,p} \in \{ 0, 1 \}$ 上記は0-1整数変数を意味している。 変数の意味は $v_{u,n,c,p} $ が 1 の時は、「ユーザー u に対する n 番目のレコメンドでカテゴリー c の価格帯 p に属するアイテムを選ぶ」ということである。 - 目的関数 $s_{u,c,p} $ によってユーザー u のカテゴリー c、価格帯 p に属するアイテムを選んだ際のスコアを表す。この最適化問題においては定数として取り扱う。 目的関数はスコア合計ということで $\sum_{u,n,c,p}{s_{u,c,p}\cdot v_{u,n,c,p}}$ とする。 (実際にレコメンドをする人の感覚にあっているかどうかは難しい問題なのでここでは問わない。業務では重要だが。線形でないと整数計画問題はなかなか解けないという理由もある。) - 制約 二種類の制約がある。 - 一度に勧められるアイテムは一つだけ $\sum_{c,p}v_{u,n,c,p} = 1, \forall u \forall n$ - 出現割合をある一定の範囲にする $r_{c,p} \in [0,1]$ をカテゴリー c、価格帯 p の希望出現割合を表す定数とする。 $\rho \in [0,1]$ を許容割合を表す定数とする。 　$ (1-\rho)\cdot r_{c,p}\cdot U\cdot N \le \sum_{u,n}v_{u,n,c,p} \le (1+\rho)\cdot r_{c,p}\cdot U\cdot N, \forall c \forall p$ r が割合なのでレコメンド総数を表す $U\cdot N $ を掛けている。 - まとめ Maximize $\sum_{u,n,c,p}{s_{u,c,p}\cdot v_{u,n,c,p}}$ such that $\sum_{c,p}v_{u,n,c,p} = 1, \forall u \forall n$ $ (1-\rho)\cdot r_{c,p}\cdot U\cdot N \le \sum_{u,n}v_{u,n,c,p} \le (1+\rho)\cdot r_{c,p}\cdot U\cdot N, \forall c \forall p$ # ortools による記述 - 最適化を解いてくれるソルバーを生成 ソルバーの生成 ``` import ortools # ソルバー生成 from ortools.linear_solver import pywraplp solver = pywraplp.Solver('Select', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING) ``` - 変数を設定 先ほど生成した solver のメソッドを使って生成する。引数の 0, 1 はそれぞれ変数の下限、上限を表す、三つ目の引数はデバッグ用に変数につける名前。 variables という変数に保存しているがこれは後々制約式、目的関数を作るのに参照が必要になるからである。 変数設定 ``` variables = OrderedDict() # 変数を設定 for u in u_c_p_to_score: variables[u] = OrderedDict() for n in n_to_cats: variables[u][n] = OrderedDict() for c in n_to_cats[n]: variables[u][n][c] = OrderedDict() for p in u_c_p_to_score[u][c]: variables[u][n][c][p] = solver.IntVar(0, 1, 'intVar(%s,%d,%d,%d)'%(u,n,c,p) ) ``` - 目的関数を設定 u_c_p_to_score　は $s_{u,c,p}$ を表す辞書。 n_to_cats は n 回目に選ぶカテゴリーのリストを表す辞書。 solver.Maximaize で最大化する式を設定する。 目的関数設定 ``` obj_terms = [] for u in u_c_p_to_score: for n in n_to_cats: for c in n_to_cats[n]: for p in u_c_p_to_score[u][c]: s = u_c_p_to_score[u][c][p] v = variables[u][n][c][p] obj_terms.append( s * v ) # solver.Sum が list の要素を足し合わせた式を返す。 obj = solver.Sum( obj_terms ) solver.Maximize( obj ) ``` - 制約設定1 不等式 cons を作るだけでは制約は設定されない。 solver.Add( cons ) とすることで問題の制約が設定される。 一つだけ選ぶ制約の設定 ``` for u in variables: for n in variables[u]: select_cons_terms = [] for c in variables[u][n]: for p in variables[u][n][c]: v = variables[u][n][c][p] select_cons_terms.append(v) cons = solver.Sum( select_cons_terms ) == 1 solver.Add( cons ) ``` - 制約設定2 c_p_w は $r_{c,p}$ rho は $\rho$ r_num は $U\cdot N $ 希望出現割合の制約の設定 ``` for c in c_p_w: for p in c_p_w[c]: rate = c_p_w[c][p] cons_terms = [] for u in variables: for n in variables[u]: if c not in variables[u][n]: # ユーザーが選べないカテゴリーは飛ばす。 continue if p not in variables[u][n][c]: # ユーザーが選べない価格帯は飛ばす。 continue cons_terms.append( variables[u][n][c][p] ) z = solver.Sum(cons_terms) lb = math.floor( (1-rho) * rate * r_num ) ub = math.ceil( (1+rho) * rate * r_num ) cons_lb = z >= lb cons_ub = z <= ub solver.Add( cons_ub ) solver.Add( cons_lb ) ``` - 求解と解出力 sover.Solve() で解く。 v.SolutionValue() で解いた答えの値を得る。 求解と解出力 ``` solver.Solve() for u in variabels: for n in variables[u]: for c in variables[u][n]: for p in variables[u][u][c]: v = variables[u][n][c][p] vv = int(v.SolutionValue()) if vv == 1: print( u,n,c,p ) ```