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 ommx-openjij-adapter to solve our model through OpenJij. ommx-openjij-adapter can be installed through pip:
pip install ommx-openjij-adapter
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 that model alone doesn’t do much besides LaTeX output. You need to combine it with instance data to generate input for the solver. First, we define the instance data to be input into the Placeholders in our model, and register that data in the Interpreter object.
You can register instance data by passing a dictionary with the following keys and values to the constructor of the Interpreter class:
Key: String set in the
nameproperty of thePlaceholderobjectValue: Data to be input
instance_data = {
"W": 100, # Data of the knapsack's weight capacity
"v": [100, 90, 80, 70, 60, 50, 40, 30], # Data of item values
"w": [1, 5, 10, 20, 30, 40, 50, 60, 70] # Data of item weights
}
interpreter = jm.Interpreter(instance_data)
To convert the mathematical model to an instance, use the Interpreter.eval_problem method. By passing the Problem object to the eval_problem method of the Interpreter object with registered instance data, the Placeholders in the Problem object will be filled with the instance data and converted to an OMMX instance:
instance = interpreter.eval_problem(problem)
Hint
The return value of Interpreter.eval_problem is an ommx.v1.Instance object. For more details about it, please refer to here.
Now we have an OMMX instance which we can use as input to the OpenJij sampler. Let’s use ommx-openjij-adapter to actually sample the problem:
from ommx_openjij_adapter import OMMXOpenJijSAAdapter
# Solve through SCIP and retrieve results as an ommx.v1.Solution
samples = OMMXOpenJijSAAdapter.sample(instance, num_reads=1)
print(f"Optimal value of the objective function: {samples.best_feasible().objective}")
Optimal value of the objective function: 329.234375
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 sample once and look at the “best” solution found.
The above samples object shows the values found by openjij for each decision variable. You can do much more to better process and visualize the results using the OMMX Adapter and OpenJij, or reuse the same mathematical model for different purposes, but please refer to their respective documentation pages for more information.