{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d1c7a815",
   "metadata": {},
   "source": [
    "# Violation Distribution (`distr_V`)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "167dd66d",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "from itertools import product\n",
    "\n",
    "from pyxla import load_data, distr_v"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99de5fa0",
   "metadata": {},
   "source": [
    "## Easy Knapsack\n",
    "\n",
    "- Large maximum weight\n",
    "- Weight and profit are uncorrelated"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "82d04ec3",
   "metadata": {},
   "outputs": [],
   "source": [
    "# number of items\n",
    "n = 10\n",
    "l_bound = 0\n",
    "u_bound = 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e7394366",
   "metadata": {},
   "outputs": [],
   "source": [
    "rng = np.random.default_rng(seed=42)\n",
    "weights = rng.integers(l_bound, u_bound, size=10) \n",
    "weights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c022a723",
   "metadata": {},
   "outputs": [],
   "source": [
    "# max weight\n",
    "max_weight = weights.sum() * 0.75"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ff8551d6",
   "metadata": {},
   "outputs": [],
   "source": [
    "profits = rng.integers(l_bound, u_bound, size=10)\n",
    "profits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cd992ed6",
   "metadata": {},
   "outputs": [],
   "source": [
    "binary_numbers = [p for p in product('01', repeat=n)]\n",
    "X = pd.DataFrame(binary_numbers).astype(int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eb096b22",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute profit\n",
    "def profit(x, profits):\n",
    "    chosen = np.where(x == 1)\n",
    "    return profits[chosen].sum()\n",
    "\n",
    "# compute violation\n",
    "def weight_violation(x, weights):\n",
    "    chosen = np.where(x == 1)\n",
    "    diff = weights[chosen].sum() - max_weight\n",
    "    return diff if diff > 0 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "42f6a678",
   "metadata": {},
   "outputs": [],
   "source": [
    "F = pd.DataFrame()\n",
    "F['f0'] = X.apply(lambda x: profit(x, profits), axis=1)\n",
    "F"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a51a0bf4",
   "metadata": {},
   "outputs": [],
   "source": [
    "V = pd.DataFrame()\n",
    "V['v0'] = X.apply(lambda x: weight_violation(x, weights), axis=1)\n",
    "V"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "886feecc",
   "metadata": {},
   "outputs": [],
   "source": [
    "easy_kp = {\n",
    "    'name': 'easy_kp',\n",
    "    'X': X,\n",
    "    'F': F,\n",
    "    'V': V,\n",
    "    max: True\n",
    "}\n",
    "\n",
    "load_data(easy_kp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e8b593d2",
   "metadata": {},
   "outputs": [],
   "source": [
    "feat, plot = distr_v(easy_kp, title=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "875be2e6",
   "metadata": {},
   "source": [
    "## Hard knapsack\n",
    "\n",
    "- Small maximum weight\n",
    "- Weight and profit are correlated"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "21771779",
   "metadata": {},
   "outputs": [],
   "source": [
    "# combination with repetition?\n",
    "rng = np.random.default_rng(seed=42)\n",
    "weights = rng.integers(l_bound, u_bound, size=10)\n",
    "weights.sort()\n",
    "weights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8b19c5a6",
   "metadata": {},
   "outputs": [],
   "source": [
    "# max weight\n",
    "max_weight = (u_bound + l_bound) / 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d0998205",
   "metadata": {},
   "outputs": [],
   "source": [
    "profits = rng.integers(l_bound, u_bound, size=10)\n",
    "profits.sort()\n",
    "profits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "59bd1516",
   "metadata": {},
   "outputs": [],
   "source": [
    "F = pd.DataFrame()\n",
    "F['f0'] = X.apply(lambda x: profit(x, profits), axis=1)\n",
    "F"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a8a20efa",
   "metadata": {},
   "outputs": [],
   "source": [
    "V = pd.DataFrame()\n",
    "V['v0'] = X.apply(lambda x: weight_violation(x, weights), axis=1)\n",
    "V"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a5a0b348",
   "metadata": {},
   "outputs": [],
   "source": [
    "hard_kp = {\n",
    "    'name': 'hard_kp',\n",
    "    'X': X,\n",
    "    'F': F,\n",
    "    'V': V,\n",
    "    max: True\n",
    "}\n",
    "\n",
    "load_data(hard_kp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "022b49ca",
   "metadata": {},
   "outputs": [],
   "source": [
    "feat, plot = distr_v(hard_kp, title=False)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": ".venv",
   "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}