We'd like to find the combination of returned goods with the heaviest total weight up to the maximum deductible amount by solving the knapsack problem, a combinatorial optimization problem, using a quantum algorithm.

Installation

!pip install qiskit_optimization
!pip install qiskit-aer
!pip install ortoolpy
!pip install pulp

Definition

from qiskit_optimization.applications import Knapsack
from qiskit.algorithms import QAOA, NumPyEigensolver, NumPyMinimumEigensolver
from qiskit.utils import QuantumInstance
from qiskit import Aer
from qiskit_optimization.algorithms import MinimumEigenOptimizer
from typing import List
from ortoolpy import knapsack
from pulp import *

deduction_amounts = []
weight = []
maximum_deduction_amount = 2300

Knapsack Problem Class

class KnapsackProblem():
    values: List[int] = []
    weights: List[int] = []
    max_weight: int = 0
    
    def __init__(self, values, weights, max_weight):
        self.values = values
        self.weights = weights
        self.max_weight = max_weight
    
    def solve_by_qaoa(self):
        problem = Knapsack(values=self.values, weights=self.weights, max_weight=self.max_weight)
        quadratic_program = problem.to_quadratic_program()
        backend = Aer.get_backend('aer_simulator')
        quantum_instance = QuantumInstance(backend=backend, shots=1024, seed_simulator=99)
        min_eigen_optimizer = MinimumEigenOptimizer(min_eigen_solver=QAOA(reps=1, quantum_instance=quantum_instance))
        result = min_eigen_optimizer.solve(quadratic_program)
        print(problem.interpret(result))
    
    def solve_by_numpy_eigensolver(self):
        problem = Knapsack(values=self.values, weights=self.weights, max_weight=self.max_weight)
        quadratic_program = problem.to_quadratic_program()
        min_eigen_optimizer = MinimumEigenOptimizer(min_eigen_solver=NumPyMinimumEigensolver())
        result = min_eigen_optimizer.solve(quadratic_program)
        print(problem.interpret(result))
    
    def solve_by_ortoolpy(self):
        result = knapsack(self.values, self.weights, self.max_weight)
        print(result)
    
    def solve_by_pulp(self):
        ran = range(len(self.values))
        problem = LpProblem(sense=LpMaximize)
        var = [LpVariable('x%d'%i, cat=LpBinary) for i in ran]
        problem += lpDot(self.weights, var)
        problem += lpDot(self.values, var) <= self.max_weight
        problem.solve()
        print((value(problem.objective), [i for i in ran if value(var[i]) > 0.5]))

Rakuten API

import requests
import numpy as np
import pandas as pd
import time

REQUEST_URL = "https://app.rakuten.co.jp/services/api/IchibaItem/Search/20170706"
APP_ID=<APP_ID>

serch_keyword = 'ふるさと納税 訳あり'
serch_params = {
    "format" : "json",
    "keyword" : serch_keyword,
    "applicationId" : [APP_ID],
    "availability" : 0,
    "hits" : 30,
    "sort" : "standard",
    "postageFlag" : 1
}

item_list = []
max_page = 10
for page in range(1, max_page+1):
    serch_params['page'] = page
    response = requests.get(REQUEST_URL, serch_params)
    result = response.json()
    
    item_key = ['itemName', 'itemPrice', 'itemCaption', 'shopName', 'shopUrl', 'itemUrl']
        
    for i in range(0, len(result['Items'])):
        time.sleep(1)
        tmp_item = {}
        item = result['Items'][i]['Item']
        for key, value in item.items():
            if key in item_key:
                tmp_item[key] = value
        item_list.append(tmp_item.copy())

df = pd.DataFrame(item_list)
df = df.reindex(columns=['itemName', 'itemPrice', 'itemCaption', 'itemUrl', 'shopName', 'shopUrl'])
df.columns = ['商品名', '商品価格', '商品説明文', '商品URL', '店舗名', '店舗URL']
df.index = df.index + 1

kg_flg = df['商品名'].str.contains('kg')
df = df[kg_flg]

df['kg'] = df['商品名'].str.extract('([0-9]+)kg')
df =df.reindex(columns=['商品名', 'kg', '商品価格', '商品説明文', '商品URL', '店舗名', '店舗URL'])

Result

df.head()

weights = df['kg'].tolist()
prices = df['商品価格'].tolist()
max_deduction = 34000 # 控除上限額
knapsack_problem = KnapsackProblem(values=weights, weights=prices, max_weight=max_deduction)
result = knapsack_problem.solve_by_qaoa()

df.iloc[result]

Reference

・https://qiita.com/SaitoTsutomu/items/bfbf4c185ed7004b5721
・https://qiita.com/massa-potato/items/831ace8b4527d90653a8
・https://qiskit.org/documentation/optimization/locale/ja_JP/tutorials/09_application_classes.html