CQM does not generate feasible solutions

Hello D-Wave community,

I am trying to solve a Constrained Quadratic Model using the Leap Hybrid CQM Sampler. My problem is that it does not generate any feasible solutions.

I am maximizing an information entropy function (reformulated it to minimization) for which I implemented Special Ordered Set constraints to create a piecewise linear approximation of the log function (possible log x values range between 0 and 100). Kind of similar to this post: https://support.gurobi.com/hc/en-us/articles/360013421331-How-do-I-model-piecewise-linear-functions-

I am working with spatial data. More specifically, I have 5 agricultural fields, and each field does have a specific area within one or more of my 4 blocks. That is stated in my block_dict. I want to assing each field one of three crop types in a way that maximizes the sum of information entropy, which is calculated for each block and then summed. The area of each block summes up to 100.

The three constraints wihtin the (second) loop allow me to use a piecewise linear approximation of the log function, which is computed before.

Here is my Code:

from dimod import ConstrainedQuadraticModel, Integer, Binary
from math import log
cqm = ConstrainedQuadraticModel()
block_dict = {0: [50, 50, 0, 0, 0], 1: [20, 10, 0, 20, 50], 2: [0, 40, 40, 20, 0], 3: [0, 10, 0, 90, 0]}
n_fields = len(block_dict[1])
num_blocks = len(block_dict.items())
crops_0 = [Binary(f'crop0_field_{i}') for i in range(n_fields)]
crops_1 = [Binary(f'crop1_field_{i}') for i in range(n_fields)]
crops_2 = [Binary(f'crop2_field_{i}') for i in range(n_fields)]

for field in range(n_fields):
# one hot constraint
cqm.add_discrete_from_model(crops_0[field] + crops_1[field] + crops_2[field], label='one_crop_type_field_' + str(field))

log_input = list(range(0, 101))
log_output = [int(log(i / 100) * 100) for i in range(1, 101)]
log_output.insert(0, 0)


for block in range(num_blocks):
sum_of_crop_0 = [crop * block_dict[block][field] for field, crop in enumerate(crops_0)]
# we need to add one to be able to sat the constraints off by setting the indicator to 0
pixels_per_block = 100 + 1

######################################################
log_crop_0_indicator = [Binary('{0}'.format('log_ind_crop_0_block_' + str(block) + '_pix_' + str(i))) for i in
range(pixels_per_block)]
log_crop_0_value = Integer(f'logV_crop0_block_{block}', lower_bound=0, upper_bound=500)

cqm.add_constraint(
sum([log_crop_0_indicator[pixel] * log_input[pixel] for pixel in range(pixels_per_block)]) - sum(
sum_of_crop_0[:]) == 0)
# Log values are negativ -> we need to add the log_crop_0_value
cqm.add_constraint(sum([log_crop_0_indicator[pixel] * log_output[pixel] for pixel in
range(pixels_per_block)]) + log_crop_0_value == 0)

cqm.add_discrete(sum(log_crop_0_indicator), 'hot_x_crop0_block_' + str(block))
######################################################
.
.
.
same for crop_1
.
same for crop_2

When sampling this even without the objective function, it does not generate any feasible solutions. Is there something wrong with the way I implemented the log_crop_0_indicator or log_crop_0_value constraint?

Best regards and thanks for your help,

 

0

Comments

1 comment
  • Hello,

    I have communicated your problem to some of my colleagues, and after some discussion they had the following feedback:

    The full model of the piecewise linear function using special order set (SOS) type 2 constraints requires both continuous and binary decision variables.  The continuous variables are needed to control the value of the x coordinate.  Binary decision variables are needed to select the segment of the piecewise linear function.  Using both the continuous and binary decision variables, multiple individual constraints are required to fully implement the SOS type 2 model.  In particular, it is necessary to enforce the conditions that the continuous variables sum to one (linear interpolation condition), that at most two are chosen (interpolate between two data points), and that the 2 selected interpolation points are contiguous (interpolation occurs between neighboring data points).  This makes the SOS type 2 formulation fairly involved, but it may have the advantage of producing a model that uses only linear terms.  A good explanation of the SOS type 2 constraints, with a simple example, is here: https://homepages.rpi.edu/~mitchj/handouts/piecewise/.  Other formulations that are simpler may be possible, but at the cost of using quadratic terms in the model.

    Hopefully this helps get you closer to your solution. Please do reach out to us if you have any additional questions.

    0
    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post