Skip to main content

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 use mathematical models and instance data provided by JijBench.

import jijmodeling as jm
import jijbench as jb

problem = jb.get_problem('Knapsack')
problem
Problem: knapsackmini=0num_items1valuesixis.t.knapsack_constraint:i=0num_items1weightsixicapacity0,xi0{0,1}\begin{alignat*}{4}\text{Problem} & \text{: knapsack} \\\min & \quad - \sum_{ i = 0 }^{ \mathrm{num\_items} - 1 } values_{i} \cdot x_{i} \\\text{s.t.} & \\& \text{knapsack\_constraint} :\\ &\quad \quad \sum_{ i = 0 }^{ \mathrm{num\_items} - 1 } weights_{i} \cdot x_{i} - capacity \leq 0,\\[8pt]& x_{i_{0}} \in \{0, 1\}\end{alignat*}

We would like to deal with the problem which has 10 items here. The instance data is in JijBench and we can get the instance data with jb.get_instance_data('Knapsack')

instance_data = list(filter(lambda x: x[0] == 'f1_l-d_kp_10_269',jb.get_instance_data('Knapsack')))[0][1]
instance_data
{'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],
'num_items': 10,
'capacity': 269}

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.

results = sampler.sample_model(problem, instance_data, multipliers,fixed_variables={'x':{(8,):1,(9,):1}}, num_reads=1, search=True)

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

import numpy as np
lowest_result = results.lowest()[0]
indices, _, _ = lowest_result.record.solution['x'][0]
sum_w = np.sum([instance_data['weights'][i] for i in indices[0]])

print('Indices of x = 1: ', indices[0])
print('Value of objective function: ', lowest_result.evaluation.objective)
print('Value of constraint term: ', lowest_result.evaluation.constraint_violations['knapsack_constraint'])
print('Total weight: ', sum_w)
Indices of x = 1:  [0, 1, 2, 3, 4, 5, 6, 8, 9]
Value of objective function: [-431.0]
Value of constraint term: [0.0]
Total weight: 351.0