Compact form of a set of constraints

Specific Domains Optimization (Mathematical)
1

I have the following script that works for the case N=4.

using JuMP 
import HiGHS
m = Model(HiGHS.Optimizer);
@variable(m, x[1:4,1:8], Bin)
@variable(m, y[1:4,1:6], Bin)

@constraints(m, begin
    [j in 1:8], sum(x[r,j] for r in 1:4)==1

    [i in 1:3],   y[4,i]-->{x[4,i]+x[4,i+5]==2}
       sum(y[4,j] for j in 1:3)==1
    [i in 1:4],   y[3,i]-->{x[3,i]+x[3,i+4]==2}
       sum(y[3,j] for j in 1:4)==1
    [i in 1:5],   y[2,i]-->{x[2,i]+x[2,i+3]==2}
       sum(y[2,j] for j in 1:5)==1
    [i in 1:6],   y[1,i]-->{x[1,i]+x[1,i+2]==2}
       sum(y[1,j] for j in 1:6)==1
    end)
optimize!(m)
julia> value.(x)
4×8 Matrix{Float64}:
 0.0  1.0  0.0  1.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  1.0  0.0  0.0  1.0
 0.0  0.0  1.0  0.0  0.0  0.0  1.0  0.0
 1.0  0.0  0.0  0.0  0.0  1.0  0.0  0.0

Can I get a compact form that allows me to do tests for higher values ​​of N, without having to hand write all the constraints, case by case?

Is something like this, with the appropriate and correct syntax possible?


N=4
m = Model(HiGHS.Optimizer);
@variable(m, x[1:N,1:2N], Bin)
@variable(m, y[1:N,1:2(N-1)], Bin)

@constraints(m, begin
    [j in 1:2N], sum(x[r,j] for r in 1:N)==1

    for k in N-1:-1:1
    [i in 1:k],   y[k+1,i]-->{x[k1,i]+x[k+1,i+k+2]==2}
       sum(y[k+1,j] for j in 1:k)==1
    end


    end)
optimize!(m)

value.(x)
2

maybe like this?

@constraints(m, begin
    [j in 1:2N], sum(x[r,j] for r in 1:N)==1
    [k in N-1:-1:1, i in 1:k],   y[k+1,i]-->{x[k+1,i]+x[k+1,i+k+2]==2}
    [k in N-1:-1:1],    sum(y[k+1,j] for j in 1:k)==1

    end)
optimize!(m)
1 Like
3

Your second comment looks like it’s on the right track, but you might want to double check your logic.

I’d probably write your model as:

using JuMP 
import HiGHS
function main(N)
    model = Model(HiGHS.Optimizer)
    @variable(model, x[1:N, 1:2N], Bin)
    @variable(model, y[1:N, 1:2(N-1)], Bin)
    @constraints(model, begin
        [j in 1:2N], sum(x[:,j]) == 1
        [i in 1:N], sum(y[i,1:(2N-1-i)]) == 1
        [k in 1:N, i in 1:(2N-1-k)], y[k,i] --> {x[k,i] + x[k,i+k+1] == 2}
    end)
    optimize!(model)
    assert_is_solved_and_feasible(model)
    return value.(x), value.(y)
end
4

Yes, of course. That was to confirm that the syntax was valid.
I put it that way.
Why does the solution x (declared Bin) have real values ​​and not integers?

m = Model(HiGHS.Optimizer);
@variable(m, x[1:N,1:2N], Bin)
@variable(m, y[1:N,1:2(N-1)], Bin)

@constraints(m, begin
   [k in 1:N, i in 1:2N-k-1],   y[k,i]-->{x[k,i]+x[k,i+k+1]==2}
   [k in 1:N],    sum(y[k,i] for i in 1:2(N-1)-k+1)==1
   [j in 1:2N], sum(x[r,j] for r in 1:N)==1
    end)
optimize!(m)

round.(Int,value.(x))

What role does this expression have?

assert_is_solved_and_feasible(model)
5

Because Optimizers work with float64.

A normality check. See the docstring.

help?> JuMP.is_solved_and_feasible
  is_solved_and_feasible(
      model::GenericModel;
      allow_local::Bool = true,
      allow_almost::Bool = false,
      dual::Bool = false,
      result::Int = 1,
  )

.....

    •  the primal_status of the result index result is FEASIBLE_POINT.

  This function is conservative, in that it returns false for situations like the solver terminating with a feasible solution due to a time      
  limit.

  If this function returns false, use termination_status, result_count, primal_status and dual_status to understand what solutions are
  available (if any).

  See also: assert_is_solved_and_feasible.
6

in my system it is not defined (I probably need to update)

ERROR: UndefVarError: `assert_is_solved_and_feasible` not defined

I provide some more information on the problem.
I was trying to understand for which values ​​of N it is possible to find a sequence of 2N numbers, containing all the pairs (1,1) (2,2) …(N,N) positioned at a distance equal to the number. For example (1,x,1), (3,x,x,x,3) …
in the case N=11

[1:11...]'*main(11)
...
 6  8  10  11  1  2  1  6  2  7  8  9  5  10  4  11  3  7  5  4  3  9
7

Take a read of Tolerances and numerical issues · JuMP

And yes, you must have an old version of JuMP. It should work after updating.

1 Like