trabalho-03.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "# Estudo de caso: \n",
    "\n",
    "## Alocação de Incentivos para Usuários e Motoristas da Lyft\n",
    "\n",
    "A figura abaixo ilustra um exemplo hipotético de um problema de alocação de incentivos: dado um grupo elegível de clientes ou motoristas, um conjunto de incentivos e um orçamento, queremos alocar os incentivos aos clientes ou motoristas para maximizar métricas incrementais, como viagens ou horas de condução.\n",
    "<img style=\"float: center;\" src=\"https://miro.medium.com/max/1400/1*mISAbI2U6iU2yNAqj3FxTQ.png\" width=\"75%\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "A alocação de incentivos é um tema comum na Lyft. Por exemplo, a empresa envia cupons promocionais aos clientes e bônus aos motoristas, na esperança de otimizar funções com o objetivo de maximizar o número de viagens ou o número de horas de condução. Nesse contexto, as principais restrições são (1) uma restrição orçamentária total sobre quanto podemos gastar com os incentivos e, às vezes (2) uma exigência de que cada cliente ou motorista possa receber apenas um incentivo no máximo. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "Tais problemas de alocação podem ser facilmente formulados como problemas de **programação inteira**, que podem ser mais relaxados para serem lineares. Embora esses problemas possuam estruturas simples, seu tamanho pode facilmente aumentar (por exemplo, pode haver muitos incentivos ou uma grande base de clientes). Então, nos perguntamos: existe uma maneira rápida e eficiente de resolver esse problema que pode superar os **Solvers** de código-fonte aberto? A resposta é sim. Nesse caso de uso específico, foi desenvolvido um algorítmo baseado na **teoria da dualidade**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "Na Lyft, os cientistas resolvem os mais diversos tipos de problemas de otimização. Embora os **Solvers** possam ser úteis, há momentos em que problemas complicados ou em larga escala precisam ser simplificados e resolvidos com algoritmos personalizados e mais eficientes. Neste caso, veremos como os cientistas da Lyft usaram a dualidade de programação linear para transformar e resolver um problema de alocação de incentivos. Para saber mais detalhes sobre como a Lyft utilizou a **Teoria da Dualidade** de **Programação Linear** para resolver o problema **10x** mais rápido do que utilizando **Solvers** convencionais [veja aqui](https://eng.lyft.com/how-to-solve-a-linear-optimization-problem-on-incentive-allocation-5a8fb5d04db1)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "Daqui em diante, você deverá encontrar a solução **Primal** e **Dual** utilizando os **Solver** de Programação Linear Inteira CBC_MIXED_INTEGER_PROGRAMMING.\n",
    "\n",
    "## Formulação de problema\n",
    "Por uma questão de simplicidade, vamos considerar um cenário de distribuição de cupons aos clientes apenas. \n",
    "\n",
    "**Definimos o seguinte:**\n",
    "<img style=\"float: center;\" src=\"https://miro.medium.com/max/1400/1*KrbFUz2QleRSyAYy-0Qhtg.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## Primal\n",
    "<img style=\"float: center;\" src=\"https://miro.medium.com/max/1400/1*_5K88oTSRTSSKR7fI2uBow.png\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "#include <iostream>\n",
    "#include <random>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "#include \"setup.h\"\n",
    "#include \"ortools/linear_solver/linear_solver.h\"\n",
    "#include \"ortools/linear_solver/linear_solver.pb.h\"\n",
    "\n",
    "using namespace operations_research;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## Crie uma variável para o cliente (rider) i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "source": [
    "## Crie uma variável para o cupom do tipo j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "source": [
    "## Crie uma constante para o total de m clientes (riders), use m=100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "source": [
    "## Crie uma constante para o número máximo de tipos de cupons distintos, use k=10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## Para cada cliente (rider) i = 1,...,m, há $k_i$ tipos distintos de cupons que podem ser atribuídos a cada cliente. Observe que $k_i$ pode ser diferente para cada cliente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## Defina $x_{ij}$, onde i=1,...,m; e j=1,...,$k_i$, como uma variável binária indicando se o cliente i recebe um cupom do tipo j. Utilize vetores para armazenamento."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## Para cada cliente (rider) i e tipo de cupom j, há um valor associado $v_{ij}$, onde i=1,...,m; e j=1,...,$k_i$. Utilize vetores para armazenamento."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## Para cada cliente (rider) i e tipo de cupom j, há um custo associado $c_{ij}$, onde i=1,...,m; e j=1,...,$k_i$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## Observe nos dados aleatórios gerados abaixo que alguns clientes (riders) não têm todos os tipos de incentivos k, mas apenas os primeiros $k_i$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "std::default_random_engine generator;  \n",
    "std::uniform_int_distribution<int> uniform_dist(0, 100);\n",
    "std::uniform_int_distribution<int> incentives_dist(1, k);\n",
    "\n",
    "for(i=0; i < m; i++) {\n",
    "    k_i[i] = incentives_dist(generator);\n",
    "    for(j=0; j < k; j++) {\n",
    "        v[i][j] = uniform_dist(generator);\n",
    "        c[i][j] = uniform_dist(generator);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## Considere um orçamento C, que limita o custo total que pode ser incorrido em uma tarefa viável. $C = \\frac{\\sum c_{ij}}{2k}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## Crie o resolvedor MIP com o back-end CBC."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## Defina as combinações de variáveis $x_{ij}$ que não possuam todos os tipos de cupons disponívels com limite superior 0 para eliminá-las do espaço de solução. Isso pode ser usado pelo solucionador na etapa de pré-resolução, reduzindo o tamanho do modelo. As variáveis que possuem cupons disponíveis são aquelas que $k_i < k$ e, nesse caso, o limite inferior deve ser 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## Crie a restrição de orçamento usando o C calculado acima"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## Crie restrições para que cada cliente possa ser receber no máximo um cupom ao todo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## Crie a função objetivo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "source": [
    "## O objetivo é maximizar o valor total dos cupons atribuídos."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## Verifique se o problema tem uma solução ótima e imprima seu valor."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## Monte um histograma numa tabela 10x1 com todos os cupons distribuidos k. Conte o número de vezes que $x_{ij}==1$ para cada j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## Verifique se os dados resultantes satisfazem as restrições (custo <= C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## Verifique se o valor total da resposta é igual à função objetivo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## Verifique se cada cliente recebeu apenas um cupom no máximo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "**Definimos o seguinte:**\n",
    "<img style=\"float: center;\" src=\"https://miro.medium.com/max/1400/1*ES8QjWf5Xe_v5mprEiRELQ.png\">\n",
    "\n",
    "## Dual\n",
    "<img style=\"float: center;\" src=\"https://miro.medium.com/max/1400/1*nWbaZVpT_fjXDQYDo7P2Tg.png\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++14",
   "language": "C++14",
   "name": "xcpp14"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}