Fixing Variable Values

In some cases, the values of some decision variables are given or known before the optimization calculation. If you are so, it is better to fix the values because the size of the solution space becomes much smaller. The feature to fix the variables before the optimization problem in JijZept is fixed_variables. This document explains how to use fixed_variables which JijZept Samplers have.

We use the knapsack problem as an example. We can write the knapsack problem using JijModeling as follows:

import jijmodeling as jm

num_items = jm.Placeholder("num items")
capacity  = jm.Placeholder("capacity")
values    = jm.Placeholder("values",  ndim=1)
weights   = jm.Placeholder("weights", ndim=1)

x = jm.BinaryVar("x", shape=(num_items,))
i = jm.Element("i", belong_to=num_items)

problem = jm.Problem("Knapsack", sense=jm.ProblemSense.MAXIMIZE)
problem += jm.sum(i, values[i] * x[i])
problem += jm.Constraint("knapsack_constraint", jm.sum(i, weights[i] * x[i]) <= capacity)

problem

$$\begin{array}{cccc} \text{Problem:} & \text{Knapsack} & & \\ & & \max \quad \displaystyle \sum_{i = 0}^{numitems - 1} values_{i} \cdot x_{i} & \\ \text{{s.t.}} & & & \\ & \text{knapsack\_constraint} & \displaystyle \sum_{i = 0}^{numitems - 1} weights_{i} \cdot x_{i} \leq capacity & \\ \text{{where}} & & & \\ & x & 1\text{-dim binary variable}\\ \end{array}$$

We would like to deal with the problem which has 10 items here:

instance_data = {
    'num items': 10,
    'capacity': 269,
    'weights': [55.0, 10.0, 47.0, 5.0, 4.0, 50.0, 8.0, 61.0, 85.0, 87.0],
    'values': [95.0, 4.0, 60.0, 32.0, 23.0, 72.0, 80.0, 62.0, 65.0, 46.0]
}

In this problem, the weights of items 8 and 9 are larger than the values, so normally there is no reason to put these items in the knapsack. However, let us consider the situation where we need to put items 8 and 9 in the Knapsack. We can use fixed_variable for this situation.

fixed_variable is the keyword argument of JijZept samplers. We have to pass the dictionary of variables to fixed_variable. Schematically, the dictionary has the following structure

{Decision variables: {Index: Value}}

The keys of the dictionary are Decision variables which you define by JijModeling and you can give it as strings. The values of the dictionary are the dictionary with pairs of indexes and decision variable values. The indexes are expressed as tuples. If you would like to fix the variables which do not have an index, you have to use an empty tuple (). The values have to be 0 or 1 for Binary and in the range for Integer.

The code below is the example code to put items 8 and 9 in the Knapsack.

import jijzept as jz

sampler = jz.JijSASampler(config='*** your config.toml path ***')
response = sampler.sample_model(
    problem,
    instance_data,
    fixed_variables={'x':{(8,):1,(9,):1}},
    num_reads=1,
    search=True
)

We can check items 8 and 9 are in the knapsack.

sampleset = response.get_sampleset()
for sample in sampleset:
    print(sample.var_values)

{'x': SparseVarValues(name="x", values={(2,): 1, (5,): 1, (8,): 1, (9,): 1}, shape=(10,), ...)}
{'x': SparseVarValues(name="x", values={(2,): 1, (5,): 1, (8,): 1, (9,): 1}, shape=(10,), ...)}
...
{'x': SparseVarValues(name="x", values={(2,): 1, (5,): 1, (8,): 1, (9,): 1}, shape=(10,), ...)}