Constraint programming - Use variables as index for matrix

Question

I am new to or-tools and I struggle to use it, here is my problem:

Let say we have a map with 3 points '1', '2', '3' and that we have 3 names 'a', 'b', 'c'. Each points can take all name but must have one name. With that we have a matrix that says the distance between all points and another that say how many time you have to go from one name to another. The goal is to find which name to set to each point to have the least distance to do.

With code:

     'Distance matrix'             'Planning matrix'
    '1'     '2'    '3'            'a'     'b'     'c'
'1'  0       10     20         'a' 0       1       3
'2'  10      0      30         'b' 1       0       2
'3'  20      30     0          'c' 3       2       0

Here we need to go from a to b 1 time. Here how i create my variables and constraints:

for x in range(len(planning)):
     for y in  range(len(planning)):
         var_list[x, y] = model.NewBoolVar('')

for x in range(len(planning)):
    model.AddExactlyOne(var_list[x, y] for y in range(len(planning)))
for y in range(len(planning)):
    model.AddExactlyOne(var_list[x, y] for x in range(len(planning)))

We have a matrix where each row and column have only one 1 My idea is to use this matrix to define which name is set to each point. The matrix can be this for example:

    'a''b''c'
'1'  0  1  0
'2'  0  0  1
'3'  1  0  0

And here is how i try to solve optimization, I use my var as an index for my distance matrix:

terms = []
for index_x in  range(len(planning)):
     for index_y in  range(len(planning)):
         terms.append(planning[index_x, index_y] * distance[np.where(var_list[index_x] == True)[0][0]][np.where(var_list[index_y] == True)[0][0]])
model.Minimize(sum(terms))

But it won't run because it can't find the index where var_list is True

terms.append(planning[index_x, index_y] * distance[np.where(var_list[index_x] == True)[0][0]][np.where(var_list[index_y] == True)[0][0]])
IndexError: index 0 is out of bounds for axis 0 with size 0

I had another idea where I use directly my variables but my problem was no longer linear:

terms = []
for index_x in  range(len(planning)):
    for index_y in  range(len(planning)):
        terms.append(
            planning[index_x, index_y] *
            sum(
                distance[i, j] * var_list[index_x, i] * var_list[index_y, j] for i in range(len(planning)) for j in range(len(planning))
            )
        )
model.Minimize(sum(terms))

Anyone know how could I change my code to make it work ? Even if I have to use another library.

You can use: github.com/google/or-tools/blob/stable/ortools/sat/docs/… — Laurent Perron
– Laurent Perron, Commented Jun 15, 2022 at 8:45
In your example p = x * y Where here i need p = distance[index_x, index_y], p is not a variable in the model — CFtrilsX
– CFtrilsX, Commented Jun 15, 2022 at 11:18
do not use integer variables, use 1 Boolean variable per value of index_x and one per value of index_y. Add sum() == 1 for all values of one variable and rewrite the model that way — Laurent Perron
– Laurent Perron, Commented Jun 15, 2022 at 11:52
Is this not what I all ready do ? (written in my question) for x in range(len(planning)): for y in range(len(planning)): var_list[x, y] = model.NewBoolVar('') for x in range(len(planning)): model.AddExactlyOne(var_list[x, y] for y in range(len(planning))) for y in range(len(planning)): model.AddExactlyOne(var_list[x, y] for x in range(len(planning))) — CFtrilsX
– CFtrilsX, Commented Jun 15, 2022 at 13:07
distance[i, j] * var_list[index_x, i] * var_list[index_y, j]. I see constant * BoolVar * BoolVar. I tell you that BoolVar*BoolVar can be replace by a new BoolVar with 3 additional clauses added to the model. — Laurent Perron
– Laurent Perron, Commented Jun 15, 2022 at 14:19

CFtrilsX · Accepted Answer · 2022-06-17 09:01:18Z

You can use: Boolean-logic_product-of-two-boolean-variables - Laurent Perron

distance[i, j] * var_list[index_x, i] * var_list[index_y, j]. I see constant * BoolVar * BoolVar. I tell you that BoolVar*BoolVar can be replace by a new BoolVar with 3 additional clauses added to the model. – Laurent Perron

Here how I have applied it:

for i in range(size**2):
    for j in range(size**2):
        var_list2[i, j] = model.NewBoolVar('')

for key_entry in range(size):
    for key_exit in range(key_entry+1, size): # I use key_entry+1 to reduce the number of constraint and keep memory because my matrix is mirrored 
        for i in range(size):
            for j in range(size):
                model.AddBoolOr(var_list[key_entry, i].Not(), var_list[key_exit, j].Not(), var_list2[i + size * key_entry, j + size * key_exit])
                model.AddImplication(var_list2[i + size * key_entry, j + size * key_exit], var_list[key_entry, i])
                model.AddImplication(var_list2[i + size * key_entry, j + size * key_exit], var_list[key_exit, j])

for key_entry in range(size):
    for key_exit in range(key_entry+1, size):
        for i in range(size):
            for j in range(size):
                terms.append(planning[key_entry, key_exit] * path_weight[i, j] * var_list2[i + size * key_entry, j + size * key_exit])

model.Minimize(sum(terms))

Albert Hendriks · Accepted Answer · 2023-07-09 13:39:40Z

0

If you want to access a variable in a 1d array using a variable index:

def AddElement(self, index, variables, target):
    """Adds the element constraint: variables[index] == target."""

https://developers.google.com/optimization/reference/python/sat/python/cp_model#addelement

answered Jul 9, 2023 at 13:39

Albert Hendriks

2,2124 gold badges31 silver badges51 bronze badges

Collectives™ on Stack Overflow

Constraint programming - Use variables as index for matrix

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related