Quantum-Inspired Optimization: The Warehouse Selection Puzzle

Python OpenJij Optimization

This repository contains a solution to the Warehouse Selection Puzzle, a combinatorial optimization problem. The project uses OpenJij, a heuristic optimization library, to solve the problem using Simulated Annealing (SA).

The problem is formulated as a QUBO (Quadratic Unconstrained Binary Optimization) model, treating the optimization landscape as a spin-glass system where constraints create "frustration" and the ground state represents the optimal shipment selection.

The objective is to select a subset of inventory items from a distribution hub to maximize total monetary value while adhering to strict operational constraints.

The facility holds exactly 100 distinct items, each defined by three attributes:

• Monetary Figure: Value in whole dollars (100ドル–1000ドル).
• Mass Value: Integer mass in kilograms (10–100 kg).
• Categorical Tag: Integer label (0–9) representing the supplier or group.

The solution must satisfy three non-negotiable rules:

1. Rule A (Mass Ceiling): The total mass of selected items must not exceed exactly 1000 kg (one metric tonne).
2. Rule B (Category Exclusivity): The shipment must not contain more than one item from the same categorical tag.
3. Rule C (Taboo Pairs): Specific pairs of items are incompatible and cannot be shipped together.

To solve this using a quantum-inspired sampler, we map the problem to a Hamiltonian (energy equation) where binary variables $x_i \in {0, 1}$ represent whether item $i$ is selected.

The total Hamiltonian $H$ to be minimized is:

$$H(x) = H_{cost} + H_{mass} + H_{cat} + H_{taboo}$$

We minimize the negative total value to maximize profit, where $P_i$ is the monetary value of item $i$: $$H_{cost} = - \sum_{i} P_i x_i$$

We use a squared penalty term to enforce the capacity limit $C = 1000$. Since standard QUBOs punish deviation from a specific number, and inequality constraints requires slack variables (which increase qubit count), this implementation uses a soft squared penalty centered on the capacity. $$H_{mass} = \lambda_{mass} \left( \sum_{i} m_i x_i - C \right)^2$$ Note: In the code, this is expanded into linear terms ($-2Cm_i$) and quadratic cross-terms (2ドルm_im_j$).

To ensure only one item is selected per category $K$, we penalize the selection if the sum of items in a category is not equal to 1: $$H_{cat} = \lambda_{cat} \sum_{k \in Categories} \left( \sum_{i \in k} x_i - 1 \right)^2$$

For every forbidden pair $(i, j)$ in the taboo list $T$, we add a large penalty if both are selected ($x_i=1$ and $x_j=1$): $$H_{taboo} = \lambda_{taboo} \sum_{(i,j) \in T} x_i x_j$$

• Language: Python
• Solver: OpenJij (Simulated Annealing Sampler)
• Data Generation: As the specific item list was not provided in the prompt, the script generates:
  • 100 items with random values ($p$), masses ($m$), and categories.
  • 25 random "Taboo Pairs" to simulate Rule C.
• Penalty Weights ($\lambda$):
  • $\lambda_{cat} = 10^{10}$ (Highest priority: Rule B is strict)
  • $\lambda_{taboo} = 10^5$
  • $\lambda_{mass} = 10^4$

Install the required dependencies:

pip install numpy pandas openjij