QUBO’s hyper parameter search - MINTO - Management and Insight Tool for Optimization

This notebook is a simple example of how to use MINTO to explore the hyperparameter space of a QUBO model. For this example, we will handle the Traveling Salesman Problem with the quadratic assignment formulation. For more details about the Traveling Salesman Problem, please refer to other resources.

import jijmodeling as jm
import matplotlib.pyplot as plt

import minto

import minto.problems.tsp

tsp = minto.problems.tsp.QuadTSP()
tsp_problem = tsp.problem()

n = 8
tsp_data = tsp.data(n=n)

tsp_problem

interpreter = jm.Interpreter(tsp_data)
instance = interpreter.eval_problem(tsp_problem)

QUBO formulation¶

E(x; A) = \sum_{i=0}^{n-1} \sum_{j=0}^{n-1} d_{ij} \sum_{t=0}^{n-1} x_{it} x_{j, (t+1)\mod n} + A \left[ \sum_i \left(\sum_{t} x_{i, t} - 1\right)^2 + \sum_t \left(\sum_{i} x_{i, t} - 1\right)^2 \right]

(1)

The parameter $A$ is a hyperparameter that controls the strength of the constraints.

In OMMX, we can tune this parameter using the .to_qubo(uniform_penalty_weight=...) method and argument uniform_penalty_weight to set the value of $A$ .

import ommx_openjij_adapter as oj_ad

parameter_values = [0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0]

experiment = minto.Experiment(auto_saving=False, verbose_logging=False)
for A in parameter_values:
    with experiment.run() as run:
        ox_sampleset = oj_ad.OMMXOpenJijSAAdapter.sample(
            instance, uniform_penalty_weight=A, num_reads=30
        )
        run.log_sampleset(ox_sampleset)
        run.log_parameter("A", A)

table = experiment.get_run_table()
table

fig, ax1 = plt.subplots()

# First y-axis for objective value
ax1.set_xlabel("Parameter A")
ax1.set_ylabel("Objective Value", color="tab:blue")
ax1.plot(
    table["parameter"]["A"], table["sampleset_0"]["obj_mean"], "-o", color="tab:blue"
)
ax1.tick_params(axis="y", labelcolor="tab:blue")

# Second y-axis for feasible count
ax2 = ax1.twinx()
ax2.set_ylabel("Feasible Count", color="tab:orange")
ax2.plot(
    table["parameter"]["A"], table["sampleset_0"]["feasible"], "-o", color="tab:orange"
)
ax2.tick_params(axis="y", labelcolor="tab:orange")

plt.title("Objective Value and Feasible Count vs Parameter A")
fig.tight_layout()