Solving Optimization Problems with OpenJij#
Let’s look at a basic example to understand how to use jijmodeling. Below, we will explain the steps to create a simple mathematical model, transform it, and run it with a solver. The first two sections are sufficient with just jijmodeling, but we recommend using Jupyter Notebook to easily check LaTeX output.
In the third section, we will use JijModelingTranspiler and OpenJij. JijModelingTranspiler and OpenJij can be installed using pip.
pip install jijmodeling-transpiler openjij
Overview#
The way to describe jijmodeling should feel natural to those familiar with mathematical optimization.
You can express formulas by combining jijmodeling classes (such as BinaryVar and Placeholder) using basic operations. The ___Var classes refer to various types of decision variables. Placeholder represents constants or values to be specified later. In other words, it abstracts the problem and marks what you want to specify as instance data. Of course, numerical literals can also be used to construct mathematical models with jijmodeling.
import jijmodeling as jm
x = jm.BinaryVar("x")
y = jm.IntegerVar("y", lower_bound=1, upper_bound=10)
n = jm.Placeholder("n")
exp = x * (y ** 2) * n
The above placeholders and variables are 0-dimensional (scalars), but you can also use these classes to represent arrays and multi-dimensional variables and constants (explained later).
In jijmodeling, you build a mathematical model by adding expressions like the above exp to a Problem object, representing the entire mathematical model. Constraints are defined by the Constraint class, which wraps comparison expressions (Constraint supports only <=, ==, and >=).
a = jm.IntegerVar("a", lower_bound=5, upper_bound=20)
b = jm.IntegerVar("b", lower_bound=1, upper_bound=20)
c = jm.IntegerVar("c", lower_bound=20, upper_bound=30)
n = jm.Placeholder("n")
problem = jm.Problem("my problem")
problem += n * (a + b + c)
problem += jm.Constraint("c1", 2 * (b + c) <= 75)
problem += jm.Constraint("c2", a + b <= 40)
problem
Creating a Model#
Let’s see how to model a common knapsack problem.
The knapsack problem is about maximizing the value of items you can carry within a weight limit \(W\) when you have \(N\) items, each with a value and weight. Below, we represent whether to carry item \(i\) with a binary variable \(x_{i}\), the weight of item \(i\) with \(w_i\), and the value of item \(i\) with \(v_i\).
First, let’s define these values with jijmodeling.
# W: Weight limit (maximum weight that can be carried)
W = jm.Placeholder("W")
# v_i: Value of item i
values = jm.Placeholder("v", ndim=1)
# w_i: Weight of item i
weights = jm.Placeholder("w", ndim=1)
# N is automatically determined based on the size of the 0th dimension of the placeholder,
# so it can be defined using the `len_at` method as follows.
# Also, for LaTeX output, we specify the `latex` parameter here.
N = values.len_at(0, latex="N")
# x_i: Binary variable representing whether to carry item i
# Here, we define a vector with N elements using the `shape` parameter.
x = jm.BinaryVar("x", shape=(N,))
# Define the index for summation.
i = jm.Element("i", (0, N))
Using the Element defined at the end of the above code, you can write summations in a style similar to sigma notation using jijmodeling.sum. In the above code, the index i is defined as the interval including 0 and excluding \(N\). It may feel strange to write this in advance, but it improves convenience by allowing reuse.
In the knapsack problem, you need to maximize the value of the items you carry while satisfying the weight limit. This can be expressed in jijmodeling as follows.
problem = jm.Problem("knapsack", sense = jm.ProblemSense.MAXIMIZE)
problem += jm.sum(i, values[i] * x[i])
problem += jm.Constraint("weight limit", jm.sum(i, weights[i] * x[i]) <= W)
problem
Expressions in jijmodeling can be stored in variables like regular Python objects. This allows you to build complex expressions from smaller ones when tackling large problems, making them easier to understand and modify later. While it may not be very useful for small problems like the knapsack problem, as an example, you can rewrite the above code as follows.
chosen_v = values[i] * x[i]
chosen_w = weights[i] * x[i]
sum_of_values = jm.sum(i, chosen_v)
sum_of_weights = jm.sum(i, chosen_w)
weight_below_limit = sum_of_weights <= W
problem = jm.Problem("knapsack", sense = jm.ProblemSense.MAXIMIZE)
problem += sum_of_values
problem += jm.Constraint("weight limit", weight_below_limit)
problem
The models represented by these two codes are equivalent. Feel free to describe the model according to your preference and convenience.
Solving the Model#
With the above code, we were able to build a model, but jijmodeling alone doesn’t do much besides LaTeX output. You need to combine it with instance data to generate input for the solver. As an example, let’s see how to transform the mathematical model built with jijmodeling into a QUBO using the freely available JijModelingTranspiler and solve the model using OpenJij. Note that tools provided by JijZept also accept mathematical models built with jijmodeling as input.
This section aims to provide a simple demonstration, so we won’t explain JijModelingTranspiler or OpenJij in detail. Please refer to their respective documentation for more information.
Below, we use JijModelingTranspiler to transform the mathematical model built with jijmodeling and instance data into a QUBO.
from jijmodeling_transpiler.core import compile_model
from jijmodeling_transpiler.core.pubo import transpile_to_pubo
data = {
"W": 100,
"v": [100, 90, 80, 70, 60, 50, 40, 30],
"w": [1, 5, 10, 20, 30, 40, 50, 60, 70]
}
compiled = compile_model(problem, data)
qubo, _ = transpile_to_pubo(compiled).get_qubo_dict()
Now we have obtained a QUBO that can be accepted as input by OpenJij. Writing out QUBOs manually is prone to errors, but using jijmodeling and jijmodeling_transpiler eliminates such errors and makes verification easier. Let’s actually input the QUBO into openjij and solve the problem.
import openjij as oj
sampler = oj.SASampler()
response = sampler.sample_qubo(qubo, num_reads=1)
response.first
Sample(sample={0: 1, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1, 6: 0, 7: 0}, energy=-5.501111111111113, num_occurrences=1)
The above code uses simulated annealing from openjij, and num_reads=1 indicates sampling only once. By increasing the value of num_reads, you can sample multiple times and explore various results using the response object. However, for this problem, all samples reach the optimal solution, so we will sample once and look at the “best” solution found.
Sample(sample={0: 1, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1, 6: 0, 7: 0}, energy=-5.501111111111113, num_occurrences=1)
The above response object shows the values found by openjij for each decision variable. You can do much more to better process and visualize the results using JijModelingTranspiler and OpenJij, or reuse the same mathematical model for different purposes, but please refer to their respective documentation pages for more information.