CTO Challenge 2015.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CTO Challenge 2015\n",
    "\n",
    "ピザを買うときに使うクーポンの種類と枚数の最適解を求める\n",
    "\n",
    "- [LEVEL 1](https://gist.github.com/makoga/4b993248de03032036a4)\n",
    "- [LEVEL 2](https://gist.github.com/makoga/7a195de59388df32dc1d)\n",
    "- [LEVEL 3](https://gist.github.com/makoga/3253f69c544b540eab00)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## LEVEL 1\n",
    "\n",
    "整数計画問題として解けば良い\n",
    "\n",
    "### 定式化\n",
    "\n",
    "入力\n",
    "- $m \\in {\\mathbb N}$  : クーポンの種類数\n",
    "- $i \\in \\{1,....m\\}$  : クーポンの種類\n",
    "- ${\\rm CouponPrice}_i \\in {\\mathbb R_{>0}}$ クーポンの価格\n",
    "- ${\\rm CouponPosessions}_i  \\in {\\mathbb Z_{\\geq0}}$ クーポンの手持ち数\n",
    "- ${\\rm TotalPrice} \\in {\\mathbb R_{>0}}$ 金額\n",
    "\n",
    "求める変数\n",
    "- ${\\rm CouponUse}_i \\in {\\mathbb Z_{\\geq0}}$ クーポンの利用枚数\n",
    "\n",
    "\n",
    "最大化したい目的関数\n",
    "- $\\displaystyle {\\sum_{i=1}^m \\{{\\rm CouponPrice}_i \\times {\\rm CouponUse}_i}\\} - \\sum_{i=1}^m{\\rm CouponUse}_i$\n",
    "\n",
    "制約\n",
    "\n",
    "- $\\displaystyle \\sum_{i=1}^m \\{{\\rm CouponPrice}_i \\times {\\rm CouponUse_i}\\} \\leq {\\rm TotalPrice}$\n",
    "- ${\\rm CouponUse}_i \\leq {\\rm CouponPosessions_i}$\n",
    "- $\\displaystyle {\\rm TotalPrice} - 1000 \\geq \\sum_{i=1}^m {\\rm CouponUse}_i$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.2\n"
     ]
    }
   ],
   "source": [
    "import pulp\n",
    "print(pulp.__version__)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#pulp.pulpTestAll()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve_level_1(total_price, coupon_posession):\n",
    "    \"\"\"\n",
    "    Parameters\n",
    "    ==========\n",
    "    total_price : int\n",
    "        注文金額\n",
    "    coupon_posession : array(int)\n",
    "        クーポン毎の所持数\n",
    "        \n",
    "    Returns\n",
    "    =======\n",
    "    coupon_use : array(int)\n",
    "        クーポン毎の使用数\n",
    "    \"\"\"\n",
    "    # クーポン金額\n",
    "    coupon_price = [500, 200, 100]\n",
    "    m = len(coupon_price)\n",
    "\n",
    "    problem = pulp.LpProblem(sense=pulp.LpMaximize)\n",
    "    # 変数\n",
    "    coupon_use = [pulp.LpVariable('CouponUse{0}'.format(i), cat=pulp.LpInteger, lowBound=0) for i in range(m)]\n",
    "    # 問題\n",
    "    problem += pulp.lpDot(coupon_use, coupon_price) - pulp.lpSum(coupon_use)\n",
    "    # 制約条件\n",
    "    problem += pulp.lpDot(coupon_use, coupon_price) <= total_price\n",
    "    problem += total_price - 1000 >= pulp.lpSum(coupon_use)\n",
    "    for i in range(m):\n",
    "        problem += coupon_posession[i] - coupon_use[i] >= 0\n",
    "    \n",
    "    status = problem.solve(pulp.get_solver('PULP_CHOCO_CMD'))\n",
    "    print(pulp.LpStatus[status])\n",
    "    #print(problem)\n",
    "    return [coupon_use[i].value() for i in range(m)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimal\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[2.0, 1.0, 0.0]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solve_level_1(1210, [2, 1, 3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimal\n",
      "Optimal\n",
      "Optimal\n",
      "Optimal\n",
      "Optimal\n"
     ]
    }
   ],
   "source": [
    "# テストケース\n",
    "assert solve_level_1(1000, [2, 1, 3]) == [0, 0, 0]\n",
    "assert solve_level_1(1210, [0, 0, 0])  == [0, 0, 0]\n",
    "assert solve_level_1(1210, [2, 1, 3])  == [2, 1, 0]\n",
    "assert solve_level_1(1530, [2, 1, 3])  == [2, 1, 3]\n",
    "# 枚数が一番小さい組み合わせを選択する事の確認\n",
    "assert solve_level_1(1500, [3, 15, 15])  == [3, 0, 0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## LEVEL 2\n",
    "\n",
    "入力値の追加 or 変更\n",
    "\n",
    "- $\\text {CouponPrice}_i := (500, 200, 100, 300)$ : クーポン価格ベクトル\n",
    "- $j \\in \\{1,....7\\}$ : メニューの種類\n",
    "- $\\text {MenuPrice} := (1000, 1500, 1300, 1800, 400, 500, 600)$ : メニューの価格ベクトル\n",
    "- $\\text {IsPizza} := (1, 1, 1, 1, 0, 0, 0)$ : ピザフラグベクトル\n",
    "- $\\text {Order}_j \\geq 0$ : 各メニューの注文数\n",
    "- $\\text {TotalPrice} := \\sum_{j=1}^{7}\\{\\text{MenuPrice}_j \\times \\text{Order}_j\\}$ : 注文金額\n",
    "\n",
    "\n",
    "追加制約\n",
    "- $\\text{CouponUse}_1 \\leq 2$\n",
    "- $\\text{CouponUse}_2 \\leq 2$\n",
    "- $\\text{CouponUse}_3 \\leq 3$\n",
    "- $\\text{CouponUse}_4 \\leq 1$\n",
    "- $\\text{CouponUse}_4 \\leq \\sum_{j=1}^{7}\\{\\text{Order}_j \\times \\text{IsPizza}_j\\}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve_level_2(order, coupon_posession):\n",
    "    \"\"\"\n",
    "    Parameters\n",
    "    ==========\n",
    "    order : array(int)\n",
    "        注文 (メニュー毎の注文数を表現するベクトル)\n",
    "    coupon_posession : array(int)\n",
    "        クーポン所持数\n",
    "        \n",
    "    Returns\n",
    "    =======\n",
    "    coupon_use : array(int)\n",
    "        クーポン毎の使用数\n",
    "    \"\"\"\n",
    "    # クーポン金額\n",
    "    coupon_price = [500, 200, 100, 300]\n",
    "    m = len(coupon_price)\n",
    "    # メニュー価格\n",
    "    menu_price = [1000, 1500, 1300, 1800, 400, 500, 600]\n",
    "    # Pizzaフラグ\n",
    "    is_pizza = [1, 1, 1, 1, 0, 0, 0]\n",
    "    # 支払い金額\n",
    "    total_price = np.dot(menu_price, order)\n",
    "\n",
    "    problem = pulp.LpProblem(sense=pulp.LpMaximize)\n",
    "    # 変数\n",
    "    coupon_use = [pulp.LpVariable('CouponUse{0}'.format(i), cat=pulp.LpInteger, lowBound=0) for i in range(m)]\n",
    "    # 問題\n",
    "    problem += pulp.lpDot(coupon_use, coupon_price) - pulp.lpSum(coupon_use)\n",
    "    # 制約条件\n",
    "    problem += pulp.lpDot(coupon_use, coupon_price) <= total_price\n",
    "    problem += pulp.lpSum(coupon_use) <= (total_price - 1000) \n",
    "    for i in range(m):\n",
    "        problem += coupon_posession[i] - coupon_use[i] >= 0\n",
    "    problem += coupon_use[0] <= 2\n",
    "    problem += coupon_use[1] <= 2\n",
    "    problem += coupon_use[2] <= 3\n",
    "    problem += coupon_use[3] <= 1\n",
    "    problem += coupon_use[3] <= np.dot(order, is_pizza)\n",
    "\n",
    "    status = problem.solve()\n",
    "    print(pulp.LpStatus[status])\n",
    "    #print(problem)\n",
    "    return [coupon_use[i].value() for i in range(m)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimal\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[2.0, 1.0, 1.0, 0.0]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solve_level_2([0, 0, 0, 0, 2, 1, 0], [2, 1, 1, 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimal\n",
      "Optimal\n",
      "Optimal\n",
      "Optimal\n",
      "Optimal\n"
     ]
    }
   ],
   "source": [
    "# テストケース\n",
    "# ジェノベーゼMx1\n",
    "assert solve_level_2([1, 0, 0, 0, 0, 0, 0], [1, 1, 1, 1]) == [0, 0, 0, 0]\n",
    "# マルゲリータMx1\n",
    "assert solve_level_2([0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0]) == [0, 0, 0, 0]\n",
    "# ポテトフライx1, グリーンサラダx1\n",
    "assert solve_level_2([0, 0, 0, 0, 2, 1, 0], [2, 1, 1, 1]) == [2, 1, 1, 0]\n",
    "# マルゲリータMx1\n",
    "assert solve_level_2([0, 0, 1, 0, 0, 0, 0], [2, 1, 1, 1]) == [2, 0, 0, 1]\n",
    "# ジェノベーゼMx1, マルゲリータMx1\n",
    "assert solve_level_2([1, 0, 1, 0, 0, 0, 0], [3, 3, 4, 2]) == [2, 2, 3, 1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## LEVEL 3\n",
    "\n",
    "- ピザ2セット: ポテトフライが1増える\n",
    "- ピザL2セット: 任意のサイドオーダーを1増やせる\n",
    "- セットメニューを注文した時はクーポンが使えない、という制約は線形で表現できないので問題を2つに分ける。2つの支払い金額を比較して小さい方を最適化とする。\n",
    "\n",
    "欲しい物が満たされる時の支払い金額を最小化する\n",
    "\n",
    "入力値の追加 or 変更\n",
    "\n",
    "- $\\text {Requirements}_j \\geq 0$ : 必要なメニュー\n",
    "- $\\text {Order}_j \\geq 0$ : 注文するメニュー\n",
    "- $\\text {OrderPrice} := \\sum \\{\\text{Order}_j \\times \\text{MenuPrice}_j\\}$ : 注文金額\n",
    "- $\\text {Payout} := \\sum_j \\text{Order}_j \\times \\text{MenuPrice}_j - \\sum \\text{CouponUse}_i \\times \\text{CouponPrice}_i$ : 請求金額\n",
    "- $\\text {IsLPizza} := (0, 1, 0, 1, 0, 0, 0)$ : Lピザフラグのベクトル\n",
    "- $\\text {IsSide} := (0, 0, 0, 0, 1, 1, 1)$ : サイドメニューフラグのベクトル\n",
    "- $\\text {Poteto} := (0, 0, 0, 0, 1, 0, 0)$ : ポテトフラグのベクトル\n",
    "\n",
    "変数の追加 or 変更\n",
    "\n",
    "- $a,b,c,d \\geq 0$\n",
    "- $\\text {Piza2SetItem} := (0, 0, 0, 0, a, 0, 0)$\n",
    "- $\\text {PizaL2SetItem} := (0, 0, 0, 0, b, c, d)$\n",
    "\n",
    "\n",
    "最小化したい目的関数\n",
    "\n",
    "$\\text{Payout} + \\sum_j \\text{CouponUse}_j$\n",
    "\n",
    "追加制約\n",
    "\n",
    "- $\\displaystyle \\text{Piza2SetItem}_5 \\leq \\frac{\\sum \\text{Order}_j \\times \\text{IsPizza}_j}{2}$\n",
    "- $\\displaystyle \\sum_j \\text{PizaL2SetItem}_j \\leq \\frac{\\sum \\text{Order}_j \\times \\text{IsLPizza}_j}{2}$\n",
    "- $\\text{Requirements}_j = \\text{Order}_j + \\text{Piza2SetItem}_j + \\text{PizaL2SetItem}_j$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def _solve_level_3(requirements, coupon_posession, use_setmenu=True):\n",
    "    \"\"\"\n",
    "    Parameters\n",
    "    ==========\n",
    "    requirements : array(int)\n",
    "        欲しいメニュー (メニュー毎の注文数を表現するベクトル)\n",
    "    coupon_posession : array(int)\n",
    "        クーポン所持数\n",
    "        \n",
    "    Returns\n",
    "    =======\n",
    "    coupon_use : array(int)\n",
    "        クーポン毎の使用数\n",
    "    \"\"\"\n",
    "    #######################################################\n",
    "    # 定数\n",
    "    #######################################################\n",
    "    # クーポン金額\n",
    "    coupon_price = [500, 200, 100, 300]\n",
    "    m = len(coupon_price)\n",
    "    # メニュー価格\n",
    "    menu_price = [1000, 1500, 1300, 1800, 400, 500, 600]\n",
    "    n = len(menu_price)\n",
    "    # フラグ\n",
    "    is_pizza = [1, 1, 1, 1, 0, 0, 0]\n",
    "    is_L_pizza = [0, 1, 0, 1, 0, 0, 0]\n",
    "    is_side = [0, 0, 0, 0, 1, 1, 1]\n",
    "    poteto = [0, 0, 0, 0, 1, 0, 0]\n",
    "\n",
    "    #######################################################\n",
    "    # 定式化\n",
    "    #######################################################\n",
    "    problem = pulp.LpProblem()\n",
    "    \n",
    "    # 変数\n",
    "    order = [pulp.LpVariable('Order{0}'.format(j), cat=pulp.LpInteger, lowBound=0) for j in range(n)]\n",
    "    order_price = pulp.lpDot(order, menu_price)\n",
    "    \n",
    "    coupon_use = [pulp.LpVariable('CouponUse{0}'.format(i), cat=pulp.LpInteger, lowBound=0) for i in range(m)]\n",
    "    piza2set_item = [0, 0, 0, 0,\n",
    "                     pulp.LpVariable('Piza2SetUse', cat=pulp.LpInteger, lowBound=0),\n",
    "                     0, 0]\n",
    "    pizaL2set_item = [0, 0, 0, 0, \n",
    "                      pulp.LpVariable('PizaL2Set1', cat=pulp.LpInteger, lowBound=0),\n",
    "                      pulp.LpVariable('PizaL2Set2', cat=pulp.LpInteger, lowBound=0),\n",
    "                      pulp.LpVariable('PizaL2Set3', cat=pulp.LpInteger, lowBound=0)\n",
    "                     ]\n",
    "    payout = order_price - pulp.lpDot(coupon_use, coupon_price)\n",
    "\n",
    "    # 最小化問題\n",
    "    problem += payout - pulp.lpSum(coupon_use)\n",
    "    \n",
    "    # 制約条件\n",
    "    problem += pulp.lpDot(coupon_use, coupon_price) <= order_price\n",
    "    problem += pulp.lpSum(coupon_use) <= (order_price - 1000) \n",
    "    for i in range(m):\n",
    "        problem += coupon_posession[i] - coupon_use[i] >= 0\n",
    "    problem += coupon_use[0] <= 2\n",
    "    problem += coupon_use[1] <= 2\n",
    "    problem += coupon_use[2] <= 3\n",
    "    problem += coupon_use[3] <= 1\n",
    "    problem += coupon_use[3] <= np.dot(order, is_pizza)\n",
    "    problem += pulp.lpSum(piza2set_item)*2 <= pulp.lpDot(order, is_pizza)\n",
    "    problem += pulp.lpSum(pizaL2set_item)*2 <= pulp.lpDot(order, is_L_pizza)\n",
    "    if use_setmenu:\n",
    "        problem += pulp.lpSum(coupon_use) == 0\n",
    "    else:\n",
    "        problem += pulp.lpSum(piza2set_item) + pulp.lpSum(pizaL2set_item) == 0\n",
    "\n",
    "        \n",
    "    for j in range(n):\n",
    "        problem += order[j] + piza2set_item[j] + pizaL2set_item[j] == requirements[j]\n",
    "\n",
    "    status = problem.solve()\n",
    "    print(pulp.LpStatus[status])\n",
    "    #print(problem)\n",
    "    print(\"Order {0}\".format([o.value() for o in order]))\n",
    "    print(\"Order Price {0}\".format(order_price.value()))\n",
    "    print(\"Piza2 Set {0}\".format(pulp.lpSum(piza2set_item).value()))\n",
    "    print(\"PizaL2 Set {0}\".format(pulp.lpSum(pizaL2set_item).value()))\n",
    "    print(\"Coupon Use {0}\".format(sum([coupon_use[i].value() for i in range(m)])))\n",
    "    print('Payout {0}'.format(payout.value()))\n",
    "    return payout.value(), [coupon_use[i].value() for i in range(m)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimal\n",
      "Order [1.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0]\n",
      "Order Price 2300.0\n",
      "Piza2 Set 1.0\n",
      "PizaL2 Set 0.0\n",
      "Coupon Use 0.0\n",
      "Payout 2300.0\n",
      "Optimal\n",
      "Order [1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 0.0]\n",
      "Order Price 2700.0\n",
      "Piza2 Set 0.0\n",
      "PizaL2 Set 0.0\n",
      "Coupon Use 1.0\n",
      "Payout 2200.0\n",
      "-------------------\n",
      "Result: [1.0, 0.0, 0.0, 0.0], Payout: 2200.0\n"
     ]
    }
   ],
   "source": [
    "# inputs\n",
    "requirements = [1, 0, 1, 0, 1, 0, 0]\n",
    "coupon_posession = [1, 0, 0, 0]\n",
    "# solve \n",
    "payout1, result1 = _solve_level_3(requirements, coupon_posession, use_setmenu=True)\n",
    "payout2, result2 = _solve_level_3(requirements, coupon_posession, use_setmenu=False)\n",
    "# クーポンを使う時と、クーポンを使わずにセットメニューを使った時で支払い金額の小さい方を採用\n",
    "ret = None\n",
    "if payout1 > payout2:\n",
    "    ret = result2\n",
    "else:\n",
    "    ret = result1\n",
    "print('-------------------')\n",
    "print(f'Result: {ret}, Payout: {min(payout1, payout2)}')\n",
    "assert(ret == [1, 0, 0, 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimal\n",
      "Order [0.0, 1.0, 0.0, 1.0, 0.0, 0.0, 0.0]\n",
      "Order Price 3300.0\n",
      "Piza2 Set 0.0\n",
      "PizaL2 Set 1.0\n",
      "Coupon Use 0.0\n",
      "Payout 3300.0\n",
      "Optimal\n",
      "Order [0.0, 1.0, 0.0, 1.0, 0.0, 0.0, 1.0]\n",
      "Order Price 3900.0\n",
      "Piza2 Set 0.0\n",
      "PizaL2 Set 0.0\n",
      "Coupon Use 1.0\n",
      "Payout 3400.0\n",
      "-------------------\n",
      "Result: [0.0, 0.0, 0.0, 0.0], Payout: 3300.0\n"
     ]
    }
   ],
   "source": [
    "# inputs\n",
    "requirements = [0, 1, 0, 1, 0, 0, 1]\n",
    "coupon_posession = [1, 0, 0, 0]\n",
    "# solve \n",
    "payout1, result1 = _solve_level_3(requirements, coupon_posession, use_setmenu=True)\n",
    "payout2, result2 = _solve_level_3(requirements, coupon_posession, use_setmenu=False)\n",
    "# クーポンを使う時と、クーポンを使わずにセットメニューを使った時で支払い金額の小さい方を採用\n",
    "ret = None\n",
    "if payout1 > payout2:\n",
    "    ret = result2\n",
    "else:\n",
    "    ret = result1\n",
    "print('-------------------')\n",
    "print(f'Result: {ret}, Payout: {min(payout1, payout2)}')\n",
    "assert(ret == [0, 0, 0, 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}