{ "cells": [ { "cell_type": "markdown", "id": "d1c7a815", "metadata": {}, "source": [ "# Violation Distribution (`distr_V`)" ] }, { "cell_type": "code", "execution_count": 16, "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": 2, "id": "82d04ec3", "metadata": {}, "outputs": [], "source": [ "# number of items\n", "n = 10\n", "l_bound = 0\n", "u_bound = 100" ] }, { "cell_type": "code", "execution_count": 37, "id": "e7394366", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([ 8, 77, 65, 43, 43, 85, 8, 69, 20, 9])" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "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": 38, "id": "c022a723", "metadata": {}, "outputs": [], "source": [ "# max weight\n", "max_weight = weights.sum() * 0.75" ] }, { "cell_type": "code", "execution_count": 39, "id": "ff8551d6", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([52, 97, 73, 76, 71, 78, 51, 12, 83, 45])" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "profits = rng.integers(l_bound, u_bound, size=10)\n", "profits" ] }, { "cell_type": "code", "execution_count": 40, "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": 41, "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": 42, "id": "42f6a678", "metadata": {}, "outputs": [ { "data": { "application/vnd.microsoft.datawrangler.viewer.v0+json": { "columns": [ { "name": "index", "rawType": "int64", "type": "integer" }, { "name": "f0", "rawType": "int64", "type": "integer" } ], "ref": "9a9552f1-0d35-4194-9b16-e1f4881d594d", "rows": [ [ "0", "0" ], [ "1", "45" ], [ "2", "83" ], [ "3", "128" ], [ "4", "12" ], [ "5", "57" ], [ "6", "95" ], [ "7", "140" ], [ "8", "51" ], [ "9", "96" ], [ "10", "134" ], [ "11", "179" ], [ "12", "63" ], [ "13", "108" ], [ "14", "146" ], [ "15", "191" ], [ "16", "78" ], [ "17", "123" ], [ "18", "161" ], [ "19", "206" ], [ "20", "90" ], [ "21", "135" ], [ "22", "173" ], [ "23", "218" ], [ "24", "129" ], [ "25", "174" ], [ "26", "212" ], [ "27", "257" ], [ "28", "141" ], [ "29", "186" ], [ "30", "224" ], [ "31", "269" ], [ "32", "71" ], [ "33", "116" ], [ "34", "154" ], [ "35", "199" ], [ "36", "83" ], [ "37", "128" ], [ "38", "166" ], [ "39", "211" ], [ "40", "122" ], [ "41", "167" ], [ "42", "205" ], [ "43", "250" ], [ "44", "134" ], [ "45", "179" ], [ "46", "217" ], [ "47", "262" ], [ "48", "149" ], [ "49", "194" ] ], "shape": { "columns": 1, "rows": 1024 } }, "text/html": [ "
| \n", " | f0 | \n", "
|---|---|
| 0 | \n", "0 | \n", "
| 1 | \n", "45 | \n", "
| 2 | \n", "83 | \n", "
| 3 | \n", "128 | \n", "
| 4 | \n", "12 | \n", "
| ... | \n", "... | \n", "
| 1019 | \n", "626 | \n", "
| 1020 | \n", "510 | \n", "
| 1021 | \n", "555 | \n", "
| 1022 | \n", "593 | \n", "
| 1023 | \n", "638 | \n", "
1024 rows × 1 columns
\n", "| \n", " | v0 | \n", "
|---|---|
| 0 | \n", "0.00 | \n", "
| 1 | \n", "0.00 | \n", "
| 2 | \n", "0.00 | \n", "
| 3 | \n", "0.00 | \n", "
| 4 | \n", "0.00 | \n", "
| ... | \n", "... | \n", "
| 1019 | \n", "37.75 | \n", "
| 1020 | \n", "77.75 | \n", "
| 1021 | \n", "86.75 | \n", "
| 1022 | \n", "97.75 | \n", "
| 1023 | \n", "106.75 | \n", "
1024 rows × 1 columns
\n", "| \n", " | f0 | \n", "
|---|---|
| 0 | \n", "0 | \n", "
| 1 | \n", "97 | \n", "
| 2 | \n", "83 | \n", "
| 3 | \n", "180 | \n", "
| 4 | \n", "78 | \n", "
| ... | \n", "... | \n", "
| 1019 | \n", "560 | \n", "
| 1020 | \n", "458 | \n", "
| 1021 | \n", "555 | \n", "
| 1022 | \n", "541 | \n", "
| 1023 | \n", "638 | \n", "
1024 rows × 1 columns
\n", "| \n", " | v0 | \n", "
|---|---|
| 0 | \n", "0.0 | \n", "
| 1 | \n", "35.0 | \n", "
| 2 | \n", "27.0 | \n", "
| 3 | \n", "112.0 | \n", "
| 4 | \n", "19.0 | \n", "
| ... | \n", "... | \n", "
| 1019 | \n", "308.0 | \n", "
| 1020 | \n", "215.0 | \n", "
| 1021 | \n", "300.0 | \n", "
| 1022 | \n", "292.0 | \n", "
| 1023 | \n", "377.0 | \n", "
1024 rows × 1 columns
\n", "