Need someone to explain to me this

I am very new to Julia and will learn, but I would ask you if you can help an explain this line by line to me:

    @constraints(model, begin
        # Constraint 1 - Only one value appears in each cell
        cell[i in 1:9, j in 1:9], sum(x[i, j, :]) == 1
        # Constraint 2 - Each value appears in each row once only
        row[i in 1:9, k in 1:9], sum(x[i, :, k]) == 1
        # Constraint 3 - Each value appears in each column once only
        col[j in 1:9, k in 1:9], sum(x[:, j, k]) == 1
        # Constraint 4 - Each value appears in each 3x3 subgrid once only
        subgrid[i=1:3:7, j=1:3:7, val=1:9], sum(x[i:i + 2, j:j + 2, val]) == 1
    end)

Thanks

This seem to be some code using JuMP.jl, so I will re-file your post to the Optimization (Mathematics) category.

About the code itself, I suggest you read the documentation I linked. In special the part about constraints. I use JuMP but this code seems a little strange. The lines a[...], sum(...) == 1 are not a common pattern. I can be wrong, but it seems to (I will explain using the names in the fist line inside the begin, the rest is analogue): create a set of constraints called cell, these are 81 constraints (each combination of i in 1:9 and j in 1:9), each of these 81 constraints define that the sum of the all elements with the first and second dimensions fixed to a specific value of i and j should be equal to one. In other words, sum(x[1, 1, all possible indexes]) must be 1, sum(x[1, 2, all possible indexes]) must be 1, and so on.

2 Likes

Also, before I forget. Welcome to our community.

3 Likes

Thank you so much, for your fast and detailed answer. That piece of code I’ve submitted here was taken for JUMP examples folder (solving sudoku with MIP solver).

So if i moves through rows, j moves through columns, k should move through actual values of sudoku cell.

For me sum(x[i, j, :]) can only mean that in MIP (0 or 1) sums of all x[i,j,1…9] = 1.

Actually this is the way I should think when working with MIP problems, try to combine all dimensions (make 9 x 9 x 9 variables in this example), and filter them out with 0 or 1 by constraints.

Correct me if I am wrong, please.

My friend and I, we are trying to move AMPL coded problem to Julia, but I don’t have any background in this kind of coding.

Thank you again and have a great Friday!

1 Like

Note that the both the utility of the indexes and of the constraints is documented within the example:

We have binary variables x[i, j, k] which, if = 1, say that cell (i, j) contains
the number k. The constraints are:
 1 - Each cell has one value only
 2 - Each row contains each number exactly once
 3 - Each column contains each number exactly once
 4 - Each 3x3 subgrid contains each number exactly once

Considering the variables are binary and the problem is a MIP, it means only one variable must have a value of one and all other must have value zero. Note that integer variables may allow negative values, so this only means the same for integer variables if they are restricted to the non-negative domain.

Not exactly. Learning how to write formulations is actually half of a class that I help my advisor in the university, so I cannot condense it in just a reply. When a certain range of values represent, in fact, a set of categorical values, and there is not a real relationship of ordering between the values, many times you will want to expand some dimension to all their possible values, and use a binary variable for each value instead, together with a constraint guaranteeing only one of these has non-zero value at a time. Otherwise, if the values actually represent an amount of something (vehicles, money, croissants, etc…), many times the best representation is just an integer variable. In some cases, you will not use the representation that feels more natural because of memory constraints, this is, you will need to make do with an integer variable because expanding all values to binary variables make the model too large. There is also a lot of tricks involved, here you can see some tips. The material is using MathProg instead of Julia+JuMP but more what is said is not framework specific.

1 Like