NL Solver-Data Types-Set and List-Solution.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "37d531e1-2452-43aa-9740-572094d919b1",
   "metadata": {},
   "source": [
    "# Exercise 3: \"Set\" Variable-Knapsack Problem\n",
    "Model the following problem using the set variable (https://docs.ocean.dwavesys.com/en/latest/docs_optimization/reference/generated/dwave.optimization.model.Model.set.html)\n",
    "\n",
    "There are four items to choose from with the following weights and values:\n",
    "\n",
    "- Item 1: 10 kg; \\$5\n",
    "- Item 2: 20 kg; \\$7\n",
    "- Item 3: 5 kg; \\$2\n",
    "- Item 4: 15 kg; \\$9\n",
    "\n",
    "The knapsack has a capacity of 30 kg. Select which items to put in the knapsack to maximize the total value of included items while staying under the 30 kg weight limit."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2d561a43-b3b9-44eb-b0c8-b63386320491",
   "metadata": {},
   "source": [
    "## Create Model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "44b1d9a5-4fb8-4d92-93b3-5011d2cea758",
   "metadata": {},
   "outputs": [],
   "source": [
    "# required imports\n",
    "from dwave.optimization import Model\n",
    "\n",
    "# create blank model\n",
    "model = Model()\n",
    "\n",
    "# Add constants\n",
    "weights = model.constant([10, 20, 5, 15])\n",
    "values = model.constant([-5, -7, -2, -9])\n",
    "capacity = model.constant(30)\n",
    "\n",
    "# Add the decision variable\n",
    "items = model.set(4)\n",
    "\n",
    "# add the capacity constraint\n",
    "model.add_constraint(weights[items].sum() <= capacity)\n",
    "\n",
    "# Set the objective\n",
    "model.minimize(values[items].sum())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "815507ba-5609-4cc6-973c-2935e4b87092",
   "metadata": {},
   "source": [
    "## Solve Problem\n",
    "Send the NL Model to the LeapHybridNLSampler"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "d44ab847-cba0-400a-898b-27186929bf21",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<Future at 0x1dd2b5e4a90 state=running>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from dwave.system import LeapHybridNLSampler\n",
    "sampler = LeapHybridNLSampler()\n",
    "sampler.sample(model)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "70aff829-afb7-44bc-9eca-da90a71fc81e",
   "metadata": {},
   "source": [
    "## Check Results\n",
    "Check Objective and Variables"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "bf1aecde-6f72-4287-84e1-b107d5fad506",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Value of Selected Items: 16.0\n",
      "Index of Selected Items: [3. 2. 0.]\n",
      "Weights of Selected Items: [15.0, 5.0, 10.0]\n",
      "Values of Selected Items: [9.0, 2.0, 5.0]\n"
     ]
    }
   ],
   "source": [
    "with model.lock():\n",
    "    print(\"Value of Selected Items:\", -model.objective.state(0))\n",
    "    index_selected_items = items.state(0)\n",
    "    print(\"Index of Selected Items:\",index_selected_items)\n",
    "    \n",
    "    selected_weights = [weights.state(0).tolist()[int(i)] for i in index_selected_items.tolist()]\n",
    "    print(\"Weights of Selected Items:\",selected_weights)\n",
    "\n",
    "    selected_values = [-values.state(0).tolist()[int(i)] for i in index_selected_items.tolist()]\n",
    "    print(\"Values of Selected Items:\",selected_values)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "668cf28d-57f0-43a8-9bd5-8fbe343c1b1e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([20,  5])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Example of how two items out of 4 original items can be selected in python\n",
    "# This is the idea behind using the set variable\n",
    "import numpy as np\n",
    "weights = np.array([10, 20, 5, 15])\n",
    "weights[[1,2]]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6bd1514a-49dc-4e27-85b3-61486108099b",
   "metadata": {},
   "source": [
    "# Exercise 4: \"List\" Variable-Basic routing Problem\n",
    "Model the following problem using the set variable.\n",
    "\n",
    "Consider a problem of selecting a route for several destinations with the cost increasing on each leg of the itinerary; for the example formulated below, one can travel through four destinations in any order, one destination per day, with the transportation cost per unit of travel doubling every subsequent day.\n",
    "\n",
    "The figure below shows four destinations as dots labeled 0 to 3, and plots the least costly (green) and most costly (red) routes.\n",
    "\n",
    "Reference: https://docs.ocean.dwavesys.com/en/latest/docs_optimization/intro.html#example-implicitly-constrained-symbols"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "b3c53a7a-eb83-4c19-a07c-62449981935f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<img src=\"https://docs.ocean.dwavesys.com/en/stable/_images/best_worst_routes.png\"/>"
      ],
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.display import Image\n",
    "from IPython.core.display import HTML\n",
    "Image(url=\"https://docs.ocean.dwavesys.com/en/stable/_images/best_worst_routes.png\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8559b5ea-7991-44b2-9fc5-08f69ea30eec",
   "metadata": {},
   "source": [
    "The code snippet below defines the cost per leg and the distances between the four destinations, with values chosen for simple illustration."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "b23df3e2-da64-4391-8f9e-327ba241d07e",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "cost_per_day = [1, 2, 4]\n",
    "distance_matrix = np.asarray([\n",
    "    [0, 1, np.sqrt(10), np.sqrt(34)],\n",
    "    [1, 0, 2, np.sqrt(25)],\n",
    "    [np.sqrt(10), 3, 0, 4],\n",
    "    [np.sqrt(34), np.sqrt(25), 4, 0]])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0028bf2b-5268-4fec-b667-c6468a008220",
   "metadata": {},
   "source": [
    "## Create Model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "fda13b68-f583-47f8-bb84-35ecca347c01",
   "metadata": {},
   "outputs": [],
   "source": [
    "from dwave.optimization import Model\n",
    "model = Model()\n",
    "# Add the constants\n",
    "cost = model.constant(cost_per_day)\n",
    "distances = model.constant(distance_matrix)\n",
    "# Add the decision symbol\n",
    "route = model.list(4) #[0,1,2,3]\n",
    "\n",
    "# Optimize the objective\n",
    "model.minimize((cost * distances[route[:-1],route[1:]]).sum())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7624d042-0a84-46f9-b222-a5e2346958dd",
   "metadata": {},
   "source": [
    "## Solve Problem\n",
    "Send the NL Model to the LeapHybridNLSampler"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "5d859cb4-905e-42db-b3f4-5216ff1d7c4e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<Future at 0x1dd28bd4c50 state=running>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from dwave.system import LeapHybridNLSampler\n",
    "sampler = LeapHybridNLSampler()\n",
    "sampler.sample(model=model)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e3932546-df6b-4d2e-96de-915ead58a421",
   "metadata": {},
   "source": [
    "## Check Results\n",
    "Check Objective and Variables"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "baeeefe1-4817-4788-ae32-b537eb854519",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Objective = 14.0\n",
      "[3. 2. 1. 0.]\n"
     ]
    }
   ],
   "source": [
    "with model.lock():\n",
    "    print(f\"Objective = {model.objective.state(0)}\")\n",
    "    print(route.state(0))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}