{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Robust Knapsack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider the robust knapsack problem introduced in [1, Section 6.1]. This problem seeks to optimize the selection of items under worst-case scenarios, ensuring that the knapsack's total value is maximized while remaining feasible despite uncertainties in values. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using the same formulation as in [1], the problem can be formulated as follows:\n",
    "$$\n",
    "\\begin{array}{ll}\n",
    "\\text{maximize} & {c}^T {x} \\\\\n",
    "\\text{subject to} & {w}^T {x} \\leq b \\quad \\forall {w} \\in \\mathcal{U} \\\\\n",
    "& {x} \\in \\{0, 1\\}^n\n",
    "\\end{array}\n",
    "$$\n",
    "\n",
    "where there are $n$ items, ${x}$ are the binary decision variables, their values are denoted by ${c}$, and their weights ${w}$ belong to a box uncertainty set, where the expected weights are denoted by ${w_e}$, and their uncertainties are captured by $\\pmb{\\delta}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import cvxpy as cp\n",
    "import numpy as np\n",
    "import lropt\n",
    "\n",
    "np.random.seed(seed=1234)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We define the constants as shown below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 200 #Number of items\n",
    "b = 1000 #Capacity\n",
    "c = np.random.uniform(low=0., high=1., size=n) #Value of each item\n",
    "w_e = np.random.uniform(low=1., high=2, size=n) #Mean weight of each item\n",
    "delta = np.random.uniform(low=0., high=0.1, size=n) #Weights uncertainties"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The uncertain parameter $\\mathbf{p}$ is formulated using LROPT in the block below. We use the box uncertainty set, which is defined as follows:\n",
    "\n",
    "$$\\mathcal{U} = \\{ \\mathbf{w} \\mid \\bar{\\mathbf{w}} - \\delta \\leq \\mathbf{w} \\leq \\bar{\\mathbf{w}} + \\delta \\}$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/mj5676/Desktop/miniconda3/envs/lropt_v3/lib/python3.12/site-packages/cvxpy/utilities/torch_utils.py:61: UserWarning: torch.sparse.SparseTensor(indices, values, shape, *, device=) is deprecated.  Please use torch.sparse_coo_tensor(indices, values, shape, dtype=, device=). (Triggered internally at /Users/runner/work/pytorch/pytorch/pytorch/torch/csrc/utils/tensor_new.cpp:643.)\n",
      "  return torch.sparse.FloatTensor(i, v, torch.Size(value_coo.shape)).to(dtype)\n"
     ]
    }
   ],
   "source": [
    "uncertainty_set = lropt.Box(rho=1, a=np.diag(delta), b=w_e)\n",
    "w = lropt.UncertainParameter(n, uncertainty_set=uncertainty_set) #Uncertain parameter\n",
    "x = cp.Variable(n, boolean=True) #Optimization variable\n",
    "\n",
    "#Define and solve the problem\n",
    "objective = cp.Maximize(c@x)\n",
    "constraints = [w@x <= b]\n",
    "prob = lropt.RobustProblem(objective=objective, constraints=constraints)\n",
    "prob.solve(solver = cp.SCIP)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "1.  Bertsimas and Sim 2004 (https://pubsonline.informs.org/doi/abs/10.1287/opre.1030.0065)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "lropt_cvxpy",
   "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.12.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}