{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "#1. Inequality Constraints\n",
        "In this notebook, we will learn how to handle inequality constraints in quantum annealing. Specifically, using the \"Capacity-Constrained Knapsack Problem\" as an example, we will implement the process of converting mathematical expressions (Hamiltonians) into Python code (QUBO matrices) step-by-step."
      ],
      "metadata": {
        "id": "xZT9aHSekdqh"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## 2. Problem Definition"
      ],
      "metadata": {
        "id": "tG54-QuslJ5H"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 2.1. What is the Knapsack Problem?\n",
        "\n",
        "* There are $N$ items.\n",
        "* Each item $i$ has an assigned weight $w_i$ and value $v_i$.\n",
        "* The capacity of the knapsack is $C$.  \n",
        "**Objective:** To maximize the total value of the items placed in the knapsack such that their total weight does not exceed the capacity $C$."
      ],
      "metadata": {
        "id": "vEISGGl4lPxt"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 2.2. Standard Formulation\n",
        "\n",
        "Mathematically, this problem is described as follows:\n",
        "\n",
        "$$\n",
        "\\begin{aligned}\n",
        "& \\text{Maximize} & & \\sum_{i=0}^{N-1} v_i x_i \\\\\n",
        "& \\text{subject to} & & \\sum_{i=0}^{N-1} w_i x_i \\le C \\\\\n",
        "& & & x_i \\in \\{0, 1\\}\n",
        "\\end{aligned}\n",
        "$$"
      ],
      "metadata": {
        "id": "vYQMKjgilUEO"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 2.3. Explanation of Variables\n",
        "\n",
        "The meanings of the symbols appearing in this formula are as follows:\n",
        "\n",
        "| Symbol | Name | Description |\n",
        "| :--- | :--- | :--- |\n",
        "| **$N$** | Number of Items | The total number of items available. |\n",
        "| **$i$** | Index | The item number ($0, 1, \\dots, N-1$). |\n",
        "| **$x_i$** | **Decision Variable** | The variable we want to determine through optimization.<br>・$1$: **Include** item $i$ in the knapsack<br>・$0$: **Do not include** item $i$ in the knapsack |\n",
        "| **$v_i$** | Value | The value of item $i$ (constant). We want to maximize the sum of these values. |\n",
        "| **$w_i$** | Weight | The weight of item $i$ (constant). |\n",
        "| **$C$** | Capacity | The maximum weight the knapsack can hold (constant). |"
      ],
      "metadata": {
        "id": "8N6pyL2xlX_U"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## 3. Mathematical Model Construction (Converting Inequality to Equality)"
      ],
      "metadata": {
        "id": "eXqWLxAAl8xW"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 3.1. Objective Function\n",
        "\"Maximizing value\" is equivalent to \"minimizing negative value\".\n",
        "\n",
        "$$H_{obj} = - \\sum_{i=0}^{N-1} v_i x_i$$"
      ],
      "metadata": {
        "id": "29DJp3QhmBhQ"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 3.2. Constraints (Handling Inequalities)\n",
        "The inequality constraint \"total weight $\\le C$\" is difficult to handle directly. Therefore, we introduce auxiliary variables $y_k$ representing that \"the actual weight placed in the knapsack is $k$ kg\" to convert it into an equality constraint.\n",
        "\n",
        "Here, $k$ takes values of $1, 2, \\dots, C$, and **exactly one of the auxiliary variables $y_1, y_2, \\dots, y_C$ must be 1 (One-hot)**.\n",
        "\n",
        "The constraints are expressed as the following two penalty terms:\n",
        "\n",
        "1.  **One-hot Constraint ($H_{cost}^{(1)}$):** Exactly one of the auxiliary variables $y_k$ must be 1.\n",
        "$$H_{cost}^{(1)} = \\lambda \\left( 1 - \\sum_{k=1}^{C} y_k\\right)^2$$\n",
        "2.  **Weight Matching Constraint ($H_{cost}^{(2)}$):** The weight $k$ indicated by the selected auxiliary variable matches the actual total weight of the items.\n",
        "$$H_{cost}^{(2)} = \\lambda \\left( \\sum_{k=1}^{C} k y_k - \\sum_{i=0}^{N-1} w_i x_i \\right)^2$$\n",
        "\n",
        "($\\lambda$ is a large positive constant representing the strength of the penalty.)"
      ],
      "metadata": {
        "id": "dVeAsg2umE-e"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 3.3. Total Hamiltonian\n",
        "\n",
        "The sum of these is the energy function that we ultimately need to minimize.\n",
        "\n",
        "$$H = H_{obj} + H_{cost}^{(1)} + H_{cost}^{(2)}$$\n",
        "$$H = - \\sum_{i} v_i x_i + \\lambda \\left( 1 - \\sum_{k} y_k \\right)^2 + \\lambda \\left( \\sum_{k} k y_k - \\sum_{i} w_i x_i \\right)^2$$"
      ],
      "metadata": {
        "id": "XJqJv4PbmJv2"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## 4. Transformation of the Hamiltonian into QUBO Format\n",
        "\n",
        "To implement this in a program, we need to expand the Hamiltonian into a form consisting of products of variables (QUBO format), such as $x_i x_j$ and $y_k y_l$.\n",
        "We expand this utilizing the property of binary variables, $x^2 = x$."
      ],
      "metadata": {
        "id": "RESgUAD7mLF_"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 4.1. Objective Function $H_{obj}$\n",
        "\n",
        "Since this is already in a simple form, it directly becomes the diagonal elements $-v_i$.\n",
        "$$H_{obj} = \\sum_{i} (-v_i) x_i$$"
      ],
      "metadata": {
        "id": "75QRiYU6mOHz"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 4.2. Constraint Term 1 $H_{cost}^{(1)}$ (One-hot Constraint)\n",
        "\n",
        "Equation: $\\lambda ( 1 - \\sum_{k} y_k )^2$\n",
        "\\begin{aligned}\n",
        "H_{cost}^{(1)} &= \\lambda \\left( 1 - 2\\sum_{k} y_k + \\left(\\sum_{k} y_k\\right)^2 \\right) \\\\\n",
        "&= \\lambda \\left( 1 - 2\\sum_{k} y_k + \\left( \\sum_{k} y_k^2 + \\sum_{k \\neq l} y_k y_l \\right) \\right) \\\\\n",
        "&\\quad \\text{* Applying the binary variable property } y_k^2 = y_k \\\\\n",
        "&= \\lambda \\left( 1 - 2\\sum_{k} y_k + \\sum_{k} y_k + 2\\sum_{k < l} y_k y_l \\right) \\\\\n",
        "&= \\lambda \\left( 1 - \\sum_{k} y_k + 2\\sum_{k < l} y_k y_l \\right) \\\\\n",
        "&\\simeq \\sum_{k} (-\\lambda) y_k + \\sum_{k < l} (2\\lambda) y_k y_l \\quad \\text{(Ignoring the constant term)}\n",
        "\\end{aligned}"
      ],
      "metadata": {
        "id": "uCHpwNOImToa"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 4.3. Constraint Term 2 $H_{cost}^{(2)}$ (Weight Matching Constraint)\n",
        "\n",
        "This is the most complex part. We will divide the equation into three parts and expand them.\n",
        "$$H_{cost}^{(2)} = \\lambda \\left( \\underbrace{\\sum_{k=1}^{C} k y_k}_{A} - \\underbrace{\\sum_{i=0}^{N-1} w_i x_i}_{B} \\right)^2 = \\lambda(A^2 - 2AB + B^2)$$"
      ],
      "metadata": {
        "id": "NZ2Ccp-TmU0D"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### 4.3.1.**Part A: Squared term of auxiliary variables ($A^2$)**\n",
        "$$\n",
        "\\begin{aligned}\n",
        "\\lambda \\left(\\sum_{k} k y_k\\right)^2 &= \\lambda \\left( \\sum_{k} k^2 y_k + 2\\sum_{k < l} k l y_k y_l \\right)\n",
        "\\end{aligned}\n",
        "$$\n",
        "Mapping to matrix $Q$:\n",
        "* **$Q_{yy}$ (Diagonal):** $\\lambda k^2$\n",
        "* **$Q_{yl}$ (Cross term $k<l$):** $2 \\lambda k l$"
      ],
      "metadata": {
        "id": "X5PbRyVEmjKf"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### 4.3.2.**Part B: Squared term of item variables ($B^2$)**\n",
        "$$\n",
        "\\begin{aligned}\n",
        "\\lambda \\left(\\sum_{i} w_i x_i\\right)^2 &= \\lambda \\left( \\sum_{i} w_i^2 x_i + 2\\sum_{i < j} w_i w_j x_i x_j \\right)\n",
        "\\end{aligned}\n",
        "$$\n",
        "Mapping to matrix $Q$:\n",
        "* **$Q_{ii}$ (Diagonal):** $\\lambda w_i^2$\n",
        "* **$Q_{ij}$ (Cross term $i<j$):** $2 \\lambda w_i w_j$"
      ],
      "metadata": {
        "id": "4R6opzCDmkXS"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### 4.3.3.**Part C: Cross term ($-2AB$)**\n",
        "$$\n",
        "\\begin{aligned}\n",
        "-2\\lambda \\left(\\sum_{k} k y_k\\right) \\left(\\sum_{i} w_i x_i\\right) &= -2\\lambda \\sum_{k}\\sum_{i} k w_i y_k x_i\n",
        "\\end{aligned}\n",
        "$$\n",
        "Mapping to matrix $Q$:\n",
        "* **$Q_{yi}$ (Cross term between auxiliary and item variables):** $-2 \\lambda k w_i$"
      ],
      "metadata": {
        "id": "UdBx_vBGmpgx"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## 5. Python Implementation and Solution with OpenJij"
      ],
      "metadata": {
        "id": "-TpwqBj7n6Re"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 5.1. Installing the Required Libraries"
      ],
      "metadata": {
        "id": "687LpX3dn-NK"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "pip install openjij numpy matplotlib"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "LI65dHaklU0i",
        "outputId": "2fa78e49-9254-4bae-e04a-356f97493cd7"
      },
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Collecting openjij\n",
            "  Downloading openjij-0.11.6-cp312-cp312-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl.metadata (8.3 kB)\n",
            "Requirement already satisfied: numpy in /usr/local/lib/python3.12/dist-packages (2.0.2)\n",
            "Requirement already satisfied: matplotlib in /usr/local/lib/python3.12/dist-packages (3.10.0)\n",
            "Collecting dimod<0.13.0,>=0.9.11 (from openjij)\n",
            "  Downloading dimod-0.12.21-cp312-cp312-manylinux2014_x86_64.manylinux_2_17_x86_64.whl.metadata (4.0 kB)\n",
            "Collecting jij-cimod<1.8.0,>=1.7.0 (from openjij)\n",
            "  Downloading jij_cimod-1.7.3-cp312-cp312-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl.metadata (10.0 kB)\n",
            "Requirement already satisfied: contourpy>=1.0.1 in /usr/local/lib/python3.12/dist-packages (from matplotlib) (1.3.3)\n",
            "Requirement already satisfied: cycler>=0.10 in /usr/local/lib/python3.12/dist-packages (from matplotlib) (0.12.1)\n",
            "Requirement already satisfied: fonttools>=4.22.0 in /usr/local/lib/python3.12/dist-packages (from matplotlib) (4.61.1)\n",
            "Requirement already satisfied: kiwisolver>=1.3.1 in /usr/local/lib/python3.12/dist-packages (from matplotlib) (1.4.9)\n",
            "Requirement already satisfied: packaging>=20.0 in /usr/local/lib/python3.12/dist-packages (from matplotlib) (26.0)\n",
            "Requirement already satisfied: pillow>=8 in /usr/local/lib/python3.12/dist-packages (from matplotlib) (11.3.0)\n",
            "Requirement already satisfied: pyparsing>=2.3.1 in /usr/local/lib/python3.12/dist-packages (from matplotlib) (3.3.2)\n",
            "Requirement already satisfied: python-dateutil>=2.7 in /usr/local/lib/python3.12/dist-packages (from matplotlib) (2.9.0.post0)\n",
            "Collecting scipy<1.16,>=1.5.4 (from jij-cimod<1.8.0,>=1.7.0->openjij)\n",
            "  Downloading scipy-1.15.3-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.metadata (61 kB)\n",
            "\u001b[2K     \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m62.0/62.0 kB\u001b[0m \u001b[31m3.4 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hRequirement already satisfied: six>=1.5 in /usr/local/lib/python3.12/dist-packages (from python-dateutil>=2.7->matplotlib) (1.17.0)\n",
            "Downloading openjij-0.11.6-cp312-cp312-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl (11.9 MB)\n",
            "\u001b[2K   \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m11.9/11.9 MB\u001b[0m \u001b[31m7.3 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hDownloading dimod-0.12.21-cp312-cp312-manylinux2014_x86_64.manylinux_2_17_x86_64.whl (8.9 MB)\n",
            "\u001b[2K   \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m8.9/8.9 MB\u001b[0m \u001b[31m8.3 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hDownloading jij_cimod-1.7.3-cp312-cp312-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl (11.6 MB)\n",
            "\u001b[2K   \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m11.6/11.6 MB\u001b[0m \u001b[31m6.8 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hDownloading scipy-1.15.3-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (37.3 MB)\n",
            "\u001b[2K   \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m37.3/37.3 MB\u001b[0m \u001b[31m15.2 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hInstalling collected packages: scipy, dimod, jij-cimod, openjij\n",
            "  Attempting uninstall: scipy\n",
            "    Found existing installation: scipy 1.16.3\n",
            "    Uninstalling scipy-1.16.3:\n",
            "      Successfully uninstalled scipy-1.16.3\n",
            "Successfully installed dimod-0.12.21 jij-cimod-1.7.3 openjij-0.11.6 scipy-1.15.3\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 5.2. Importing Libraries"
      ],
      "metadata": {
        "id": "lckqH1AooHEl"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import numpy as np\n",
        "import openjij as oj"
      ],
      "metadata": {
        "id": "-Qsv7rexoBuL"
      },
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 5.3. Problem **Setup**"
      ],
      "metadata": {
        "id": "qnsAO1wDoMX7"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# ==========================================\n",
        "# Problem Setup\n",
        "# ==========================================\n",
        "# Define the list of items.\n",
        "# Each dictionary represents one item. The keys mean the following:\n",
        "#   'weight': w_i in the formula (weight)\n",
        "#   'value':  v_i in the formula (value)\n",
        "items = [\n",
        "    {'weight': 2, 'value': 3},\n",
        "    {'weight': 3, 'value': 4},\n",
        "    {'weight': 4, 'value': 5},\n",
        "    {'weight': 5, 'value': 8}, # Heavy (5kg) but high value (8). Choosing this is the key.\n",
        "    {'weight': 1, 'value': 1}\n",
        "]\n",
        "\n",
        "# For easier calculation, separate weights and values into distinct lists.\n",
        "# This allows accessing the i-th weight via weights[i] and the i-th value via values[i].\n",
        "weights = [item['weight'] for item in items]\n",
        "values = [item['value'] for item in items]\n",
        "\n",
        "# ==========================================\n",
        "# Definition of Constants and Parameters\n",
        "# ==========================================\n",
        "N = len(items)       # Total number of items (N in the formula)\n",
        "                     # -> This means item variables x_0 ... x_{N-1} are required.\n",
        "\n",
        "C = 7                # Capacity limit of the knapsack (C in the formula)\n",
        "                     # -> Total weight must be less than or equal to this (Σw_i x_i <= C).\n",
        "\n",
        "# Penalty coefficient (λ: Lambda in the formula)\n",
        "# The strength of the penalty imposed when constraints (capacity overflow or One-hot violation) are broken.\n",
        "# If this value is too small, the solver might decide \"it's more profitable to include high-value items even with the penalty,\"\n",
        "# resulting in a solution that violates the rules.\n",
        "# Therefore, we set a value sufficiently larger than the item values (here, 100.0).\n",
        "LAMBDA = 100.0\n",
        "\n",
        "# Display the setup for confirmation\n",
        "print(f\"Items (Weight, Value): {list(zip(weights, values))}\")\n",
        "print(f\"Capacity: {C}\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "7joj3DxToJ-L",
        "outputId": "6ad02ca7-2f78-4912-fc3b-e322c1bc1034"
      },
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Items (Weight, Value): [(2, 3), (3, 4), (4, 5), (5, 8), (1, 1)]\n",
            "Capacity: 7\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 5.4. Creating the QUBO Matrix"
      ],
      "metadata": {
        "id": "ZVMDy-J7pHjg"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# ==========================================\n",
        "# QUBO Matrix Initialization (Zero Matrix)\n",
        "# ==========================================\n",
        "# Create a blank (N+C) x (N+C) matrix\n",
        "Q = np.zeros((N+C, N+C))\n",
        "\n",
        "# --- Utility functions for index manipulation ---\n",
        "def get_q_idx(i):\n",
        "    \"\"\"Index in the matrix for item i (0 to N-1)\"\"\"\n",
        "    return i\n",
        "\n",
        "def get_y_idx(k):\n",
        "    \"\"\"Index in the matrix for auxiliary variable y_k (k=1 to C)\"\"\"\n",
        "    # Follows the item variables. Since k starts at 1, subtract 1 to make it 0-indexed.\n",
        "    return N + (k - 1)\n",
        "\n",
        "# ==========================================\n",
        "# Embedding into the QUBO Matrix\n",
        "# ==========================================\n",
        "\n",
        "# ------------------------------------------------\n",
        "# (A) Objective Function: Maximize value (Minimize negative value)\n",
        "# ------------------------------------------------\n",
        "for i in range(N):\n",
        "    idx = get_q_idx(i)\n",
        "    v = items[i]['value']\n",
        "    # Add -v to the diagonal component\n",
        "    Q[idx, idx] += -1 * v\n",
        "\n",
        "# ------------------------------------------------\n",
        "# (B) Constraint 1: Exactly one auxiliary variable y must be 1 (One-hot)\n",
        "# Formula: lambda * (1 - sum(y))^2\n",
        "# Expansion -> lambda * ( sum(y^2) + sum(y_i*y_j) - 2sum(y) ) + constant\n",
        "# ------------------------------------------------\n",
        "for k1 in range(1, C + 1):\n",
        "    idx1 = get_y_idx(k1)\n",
        "\n",
        "    # 1. Linear term: -2 * lambda * y_k\n",
        "    Q[idx1, idx1] += -2 * LAMBDA\n",
        "\n",
        "    # 2. Squared term diagonal component: + lambda * y_k^2 (= y_k)\n",
        "    Q[idx1, idx1] += LAMBDA\n",
        "\n",
        "    # 3. Squared term cross component: + 2 * lambda * y_k1 * y_k2\n",
        "    for k2 in range(k1 + 1, C + 1):\n",
        "        idx2 = get_y_idx(k2)\n",
        "        Q[idx1, idx2] += 2 * LAMBDA\n",
        "\n",
        "# ------------------------------------------------\n",
        "# (C) Constraint 2: Match the total weights\n",
        "# Formula: lambda * ( sum(k*y) - sum(w*q) )^2\n",
        "# Expansion -> lambda * ( A^2 - 2AB + B^2 )\n",
        "# A = sum(k*y), B = sum(w*q)\n",
        "# ------------------------------------------------\n",
        "\n",
        "# --- Part 1: A^2 (Product of auxiliary variables) ---\n",
        "# (sum k*y)^2 = sum k^2*y + sum 2*k1*k2*y1*y2\n",
        "for k1 in range(1, C + 1):\n",
        "    idx1 = get_y_idx(k1)\n",
        "    # Diagonal component (k^2)\n",
        "    Q[idx1, idx1] += LAMBDA * (k1 ** 2)\n",
        "\n",
        "    # Cross component (2 * k1 * k2)\n",
        "    for k2 in range(k1 + 1, C + 1):\n",
        "        idx2 = get_y_idx(k2)\n",
        "        Q[idx1, idx2] += LAMBDA * 2 * k1 * k2\n",
        "\n",
        "# --- Part 2: B^2 (Product of item variables) ---\n",
        "# (sum w*q)^2 = sum w^2*q + sum 2*w1*w2*q1*q2\n",
        "for i1 in range(N):\n",
        "    idx1 = get_q_idx(i1)\n",
        "    w1 = items[i1]['weight']\n",
        "    # Diagonal component (w^2)\n",
        "    Q[idx1, idx1] += LAMBDA * (w1 ** 2)\n",
        "\n",
        "    # Cross component (2 * w1 * w2)\n",
        "    for i2 in range(i1 + 1, N):\n",
        "        idx2 = get_q_idx(i2)\n",
        "        w2 = items[i2]['weight']\n",
        "        Q[idx1, idx2] += LAMBDA * 2 * w1 * w2\n",
        "\n",
        "# --- Part 3: -2AB (Product of item and auxiliary variables) ---\n",
        "# -2 * sum(k*y) * sum(w*q)\n",
        "for k in range(1, C + 1):\n",
        "    idx_y = get_y_idx(k)\n",
        "    for i in range(N):\n",
        "        idx_q = get_q_idx(i)\n",
        "        w = items[i]['weight']\n",
        "\n",
        "        # Coefficient: -2 * lambda * k * w\n",
        "        coeff = -2 * LAMBDA * k * w\n",
        "\n",
        "        # Process to place in the upper triangular part of the matrix (row < col)\n",
        "        if idx_y < idx_q:\n",
        "            Q[idx_y, idx_q] += coeff\n",
        "        else:\n",
        "            Q[idx_q, idx_y] += coeff"
      ],
      "metadata": {
        "id": "f4WFG1CioQ77"
      },
      "execution_count": 7,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 5.5. Solving with OpenJij"
      ],
      "metadata": {
        "id": "9ZNRHZcxpqN3"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# ==========================================\n",
        "# Solving with OpenJij\n",
        "# ==========================================\n",
        "print(\"Calculating optimization...\")\n",
        "sampler = oj.SQASampler()\n",
        "# num_reads: Number of calculations (higher means more stable)\n",
        "response = sampler.sample_qubo(Q, num_reads=1000)\n",
        "\n",
        "# Getting the best solution\n",
        "sample = response.first.sample\n",
        "\n",
        "# ==========================================\n",
        "# Displaying the results\n",
        "# ==========================================\n",
        "print(\"\\n\" + \"=\"*30)\n",
        "print(\" Optimization Results \")\n",
        "print(\"=\"*30)\n",
        "\n",
        "total_w = 0\n",
        "total_v = 0\n",
        "active_y = 0\n",
        "\n",
        "# --- Checking the items ---\n",
        "print(\"[Selected Items]\")\n",
        "for i in range(N):\n",
        "    idx = get_q_idx(i)\n",
        "    if sample[idx] == 1:\n",
        "        item = items[i]\n",
        "        print(f\"  ID:{i} (Weight:{item['weight']}, Value:{item['value']})\")\n",
        "        total_w += item['weight']\n",
        "        total_v += item['value']\n",
        "\n",
        "# --- Checking the auxiliary variables ---\n",
        "for k in range(1, C + 1):\n",
        "    idx = get_y_idx(k)\n",
        "    if sample[idx] == 1:\n",
        "        active_y = k\n",
        "\n",
        "print(\"-\" * 30)\n",
        "print(f\"Total Value: {total_v}\")\n",
        "print(f\"Total Weight: {total_w} / Capacity {C}\")\n",
        "print(f\"Auxiliary Variable (Target Weight): {active_y}\")\n",
        "\n",
        "if total_w <= C and total_w == active_y:\n",
        "    print(\">>> Success: Optimal solution satisfying the constraints.\")\n",
        "else:\n",
        "    print(\">>> Failure: Constraint violation occurred (possible lack of penalty).\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Vxh4dS0ioXgz",
        "outputId": "d7483a2b-0ffb-44b2-9ace-13aadf5dfb92"
      },
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Calculating optimization...\n",
            "\n",
            "==============================\n",
            " Optimization Results \n",
            "==============================\n",
            "[Selected Items]\n",
            "  ID:0 (Weight:2, Value:3)\n",
            "  ID:3 (Weight:5, Value:8)\n",
            "------------------------------\n",
            "Total Value: 11\n",
            "Total Weight: 7 / Capacity 7\n",
            "Auxiliary Variable (Target Weight): 7\n",
            ">>> Success: Optimal solution satisfying the constraints.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 5.6. Validity of the Solution\n",
        "\n",
        "First, let's verify if the constraints are satisfied.\n",
        "* **Selected items:** ID:0 (2kg) and ID:3 (5kg)\n",
        "* **Total weight:** 2 + 5 = 7 kg\n",
        "* **Capacity limit:** $C$ = 7 kg\n",
        "\n",
        "The total weight does not exceed the capacity limit ($\\le$ 7).\n",
        "Furthermore, please pay attention to the \"Auxiliary Variable (Target Weight): 7\" in the output. This means the annealing machine determined that \"the total weight of the items will be 7kg\" and correctly set the corresponding slack variable $y_7$ to 1.\n",
        "The weight of the items and the auxiliary variable are perfectly synchronized, which is evidence that the mathematical model ($H_{cost}^{(2)}$) functioned correctly."
      ],
      "metadata": {
        "id": "qnIZq88Lp6HB"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 5.7. Confirmation of Optimality\n",
        "\n",
        "Is this really the best combination (the optimal solution)? Let's compare it with other combinations.\n",
        "\n",
        "* **Pattern A (Current solution):**\n",
        "    * Item 0 (2kg, Value 3) + Item 3 (5kg, Value 8)\n",
        "    * $\\to$ Weight 7kg, **Value 11**\n",
        "* **Pattern B (Another combination example):**\n",
        "    * Item 1 (3kg, Value 4) + Item 2 (4kg, Value 5)\n",
        "    * $\\to$ Weight 7kg, **Value 9**\n",
        "* **Pattern C (Many light items):**\n",
        "    * Item 0 + Item 1 + Item 4\n",
        "    * $\\to$ Weight 6kg, **Value 8**\n",
        "\n",
        "The annealing machine has correctly searched for the combination that maximizes the value, rather than just satisfying the weight constraint."
      ],
      "metadata": {
        "id": "rt-x6oOlp9I4"
      }
    }
  ]
}