Solving Optimization Problems with OpenJij

To understand how to use jijmodeling, let’s solve the knapsack problem on this page. However, since jijmodeling is a tool for describing mathematical models, it cannot solve optimization problems on its own. Therefore, we will solve it in combination with the mathematical optimization sampler OpenJij.

To use jijmodeling with OpenJij, you need to install a Python package called ommx-openjij-adapter (GitHub, PyPI). Please install it with the following command:

pip install ommx-openjij-adapter

Problem Setting

The knapsack problem can be formulated as a mathematical model as follows:

\[\begin{split} \begin{align*} \mathrm{maximize} \quad & \sum_{i=0}^{N-1} v_i x_i \\ \mathrm{s.t.} \quad & \sum_{i=0}^{N-1} w_i x_i \leq W, \\ & x_{i} \in \{ 0, 1\} \end{align*} \end{split}\]

Hint

For more details on the formulation of the knapsack problem, please refer to here.

The meaning of each parameter in this mathematical model is as follows:

Parameter	Description
\(N\)	Total number of items
\(v_{i}\)	Value of item \(i\)
\(w_{i}\)	Weight of item \(i\)
\(W\)	Weight capacity of the knapsack

In this explanation, we will solve an instance obtained by inputting the following values into the parameters \(v_{i}, w_{i}, W\) of the above mathematical model:

Parameter	Value
\(v_{i}\)	[10, 13, 18, 31, 7, 15]
\(w_{i}\)	[11, 15, 20, 35, 10, 33]
\(W\)	47

What is an instance?

In jijmodeling, a dictionary that stores specific values for the parameters of a mathematical model is called “instance data”, and a mathematical model with specific values assigned to its parameters is called an “instance”.

Procedure for Generating an Instance

Using jijmodeling, you can generate an instance to input into the solver in the following 3 steps:

1. Formulate the knapsack problem

2. Prepare instance data

3. Generate an instance

Step1. Formulate the Knapsack Problem

Formulating the knapsack problem using jijmodeling results in the following Python code:

import jijmodeling as jm

@jm.Problem.define("Knapsack", sense=jm.ProblemSense.MAXIMIZE)
def knapsack_problem(problem: jm.DecoratedProblem):
    # Total number of items
    N = problem.Natural("N")
    # Value of items
    v = problem.Natural("v", shape=N)
    # Weight of items
    w = problem.Natural("w", shape=N)
    # Weight capacity of the knapsack
    W = problem.Natural("W")
    # Decision variable: 1 if item i is in the knapsack, 0 otherwise
    x = problem.BinaryVar("x", shape=(N,)) 

    # Objective function
    problem += jm.sum(v[i] * x[i] for i in N)
    # Constraint: Do not exceed the weight capacity of the knapsack
    problem += problem.Constraint("Weight Limit", jm.sum(w[i] * x[i] for i in N) <= W)

knapsack_problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{Knapsack}\\\displaystyle \max &\displaystyle \sum _{i=0}^{N-1}{{v}_{i}\cdot {x}_{i}}\\&\\\text{s.t.}&\\&\begin{aligned} \text{Weight Limit}&\quad \displaystyle \sum _{i=0}^{N-1}{{w}_{i}\cdot {x}_{i}}\leq W\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\v&\in \mathop{\mathrm{Array}}\left[N;\mathbb{N}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{N}\\W&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\w&\in \mathop{\mathrm{Array}}\left[N;\mathbb{N}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

Hint

For more details on how to formulate with jijmodeling, please refer to Basics.

Step2. Prepare Instance Data

Next, prepare the instance data for the parameters \(v_i, w_i, W\) of the mathematical model formulated in Step1.

instance_data = {
    "N": 6,
    "v": [10, 13, 18, 31, 7, 15],  # Data of item values
    "w": [11, 15, 20, 35, 10, 33], # Data of item weights
    "W": 47,                       # Data of the knapsack's weight capacity
}

Step3. Convert to an Instance

Finally, let’s generate an instance using the formulated mathematical model and the prepared instance data.

instance = knapsack_problem.eval(instance_data)

Hint

The return value of Problem.eval is an ommx.v1.Instance object. For more details about it, please refer to here.

Solving the Optimization Problem

Now, let’s solve the instance obtained in Step3 with OpenJij’s simulated annealing.

from ommx_openjij_adapter import OMMXOpenJijSAAdapter

# Solve the problem via OpenJij and get the solution as ommx.v1.Solution
solution = OMMXOpenJijSAAdapter.solve(
    instance,
    num_reads=100,
    num_sweeps=10,
    uniform_penalty_weight=1.6,
)

Using OMMXOpenJijSAAdapter, you can easily convert an instance defined by ommx.v1.Instance to QUBO/HUBO format using the penalty method or log encoding, and solve it. Also, the obtained solution can be displayed as a pandas.DataFrame object using the decision_variables_df property:

df = solution.decision_variables_df
df[df["name"] == "x"][["name", "subscripts", "value"]]

	name	subscripts	value
id
0	x	[0]	1.0
1	x	[1]	1.0
2	x	[2]	1.0
3	x	[3]	0.0
4	x	[4]	0.0
5	x	[5]	0.0

Note

Since OMMXOpenJijSAAdapter internally performs conversion to QUBO/HUBO format, decision variables may be added from the input instance or the objective function may be changed. Therefore, filtering elements using pandas.DataFrame as shown above is necessary.

Hint

The return value of OMMXPySCIPOptAdapter.solve is an ommx.v1.Solution object. For more details, please refer to here.