q_optimisation_problem.py

# -*- coding: utf-8 -*-
"""Q_Optimisation_Problem.ipynb

Automatically generated by Colab.

Original file is located at
    https://colab.research.google.com/drive/1FUbg9HCUIV6CAwCGKvwsVPF41aouYett
"""

pip install openjij

# Spin-Glass-Based-QUBO-Solver

""" Looking at the problem statement, I kinda understood that it is like Spin Glass Ground State Problem, where one needs to find the
Subset of items that maximizes the value while adhering to certain constraints. These Constrains are basically the conditions that cause
"Frustration" in the system. Hence this Frustration can be solved using Spin Glass based QUBO Solver. This is just my understanding of the problem"""

import numpy as np
from openjij import SASampler
import openjij as oj
import pandas as pd

#Defining the Given Problem Conditions
num_items = 100
num_categories = 10
p = np.random.randint(100, 1001, size=100)
m = np.random.randint(10, 101, size=100)
m = m.astype(float)
categories = np.repeat(np.arange(10), 10)
lambda_mass = 10000
lambda_taboo = 100000
lambda_cat = 10000000000 #10000000000 should be the minimum value to ensure that the category rule is strictly enforced anything below will violate the Category Rule

#Generating the Taboo Pairs (I didn't receive the original taboo pairs set from the problem statement, hence created random pairs)
num_taboo_pairs = 25
taboo_pairs = set()

while len(taboo_pairs) < num_taboo_pairs:
    pair = tuple(np.random.choice(100, 2, replace=False))
    taboo_pairs.add(pair)
T = list(taboo_pairs)


# Solve the QUBO using OpenJij's SQA Sampler
n = num_items
Q = {}

for i in range(n):
    Q[(i, i)] = - p[i] + lambda_mass * m[i]**2 - 2 * lambda_mass * 1000 * m[i]
    for j in range(i+1,n):
        Q[(i,j)] = 2*lambda_mass*m[i]*m[j]
        if (i, j) in taboo_pairs or (j, i) in taboo_pairs:
            Q[(i,j)] += lambda_taboo

category_dict = {}
for idx, cat in enumerate(categories):
    if cat not in category_dict:
        category_dict[cat] = []
    category_dict[cat].append(idx)

for cat_items in category_dict.values():
    for i in cat_items:
        Q[(i, i)] = Q.get((i, i), 0) - lambda_cat
        for j in cat_items:
            if i != j:
                Q[(i, j)] = Q.get((i, j), 0) + 2 * lambda_cat

Sampler = oj.SASampler()
response = Sampler.sample_qubo(Q, num_reads=1000)
best_solution = response.first.sample
selected_indices = [i for i, val in best_solution.items() if val == 1]
total_mass = np.sum([m[i] for i in selected_indices])
total_value = np.sum([p[i] for i in selected_indices])

#Checking the Rules
rule_mass = total_mass <= 1000
rule_category = True
for cat in np.unique(categories[selected_indices]):
    if np.sum(categories[selected_indices] == cat) > 1:
        rule_category = False
        break
rule_taboo = True
for (i,j) in T:
    if i in selected_indices and j in selected_indices:
        rule_taboo = False
        break

print(f"Rule A (Mass <= 1000): {'Passed' if rule_mass else 'Mass Rule Violated'}")
print(f"Rule B (Category exclusivity): {'Passed' if rule_category else 'Category Rule Violated'}")
print(f"Rule C (No taboo pairs): {'Passed' if rule_taboo else 'Taboo Rule Violated'}")
print(f"Total value: {total_value}")
print(f"Total mass: {total_mass}")

# Creating the DataFrame for the selected items
df = pd.DataFrame({
    "Item": selected_indices,
    "Value ($)": [p[i] for i in selected_indices],
    "Mass (kg)": [m[i] for i in selected_indices],
    "Category": [categories[i] for i in selected_indices]
})

total = pd.DataFrame({
    "Item": ["Total"],
    "Value ($)": [df["Value ($)"].sum()],
    "Mass (kg)": [df["Mass (kg)"].sum()],
    "Category": ["-"]
})

df = pd.concat([df, total], ignore_index=True)
print(df)