How to define a constraint from a string?

Specific Domains Optimization (Mathematical)
1

Hello,

Trying to write a Kenken solver, I am using a text string to define the problem. The first lines of the string look like this:
“”"
6
13 + A1 A2 B1 B2
180 * C1 D1 D2 E1
9 + F1 F2 F3
2 = C2
“”"

where the first line is a size of the grid.

I have been trying to create constraints using those line-by-line text strings. Is there a way to express a constraint as a string so that it can be added it to the model, or cast a string as an expression? Nothing in the docs/google gave me any clue.

I wouldn’t be surprised if others have tried to automatically convert existing models to test JuMP, so I would hope there is a way to do this.

Thank you for your help.

Manny

2

Do you need to go through those text files? why don’t you model the problem directly in JuMP?

If you really need this, probably a string macro is the way to go:

https://docs.julialang.org/en/v0.6.1/manual/metaprogramming/#Non-Standard-String-Literals-1

1 Like
3

I am using JuMP to model the problem. But I want an easy way to input different problems, hence the text string (not file) as a starting point. Also, I want to try several ideas I have to optimise the search, therefore I would need to create very different set of constraints from the same text definition.

Macros are beyond my current knowledge of Julia, and certainly look very different from the lisp macro definition I am familiar with… I will do some digging into your idea.

Thanks.

4

I spent a few hours trying to find a solution, including educating myself about string macros and reading the source code of JuMP (specifically macros.jl and affexpr.jl). To no avail.

The simplified version of the question would be: how to make this work:

@constraint(model, “x[1, 1] + x[1, 2] == 2”) were the second argument is a string and it contains indexed variables.

@constraint(model, parse(“x[1, 1] + x[1, 2] == 2”)) returns: AssertionError: length(x.args) == 3

I haven’t been able to find a way to recast the string into a constraint type, including writing a macro to generate this expression.

5

I don’t understand: why would you like to turn valid JuMP syntax into string just to parse it later to… valid JuMP syntax??

m = Model()
x = @variable(m, x[1:10, 1:10])
@constraint(m, x[1,1] + x[1,2] == 2)

works.

Could you please explain what is your overall goal? e.g. what constraint does the string in your first post is supposed to represent?

1 Like
6

Please assume that the problem is set up as per your first 2 lines (I do it differently but I don’t think this is relevant at this point).

Then, let’s imagine a simplistic problem definition like “3 * A1 A2”. This is how a problem is often expressed online.

The basic way to express that constraint is to say: “x[1,1] * x[1, 2] == 3”.
Alternatively, given all solutions as integers, this could be expressed as more constraints (with m being a binary variable):

m     * ( x[1, 1] -1) = 0
m     * ( x[1, 2] -3) = 0
(1-m) * ( x[1, 1] - 3) = 0
(1-m) * ( x[1, 2] - 1) = 0

I have no idea which solution works more efficiently (I am just playing around). But the key point is that from a single original problem definition (the “3 * A1 A2”), I want to be able to play with that original string definition to generate one or several constraints; at some point in the process, I will need to convert strings into actual constraint ‘object’ that will be accepted as such by @constraint.

Hopefully, my question is getting clearer. Happy to answer any question otherwise.

7

@constraint is a macro, it takes expressions. If, in general, you want to manipulate these expressions, you should not be working with strings, but their representation in Julia, called the abstract syntax tree. Eg

julia> ex = :(x[1,1] * x[1, 2] == 3)
:(x[1, 1] * x[1, 2] == 3)

julia> dump(ex)
Expr
  head: Symbol call
  args: Array{Any}((3,))
    1: Symbol ==
    2: Expr
      head: Symbol call
      args: Array{Any}((3,))
        1: Symbol *
        2: Expr
          head: Symbol ref
          args: Array{Any}((3,))
            1: Symbol x
            2: Int64 1
            3: Int64 1
        3: Expr
          head: Symbol ref
          args: Array{Any}((3,))
            1: Symbol x
            2: Int64 1
            3: Int64 2
    3: Int64 3

That said, working with the package’s expression representation directly may be much, much easier. I don’t know much about JuMP, but from looking at the manual, it is my impression that some of this is exposed.

8

You are correct that this is exposed. That’s why I tried to read the source code (with my basic knowledge of Julia). Above my head.

Parse(“x[1,1] * x[1, 2] == 3”) returns an expression but this is not accepted as a parameter in @constraint. See the error message I got above.

I tried the equivalent of the common lisp macroexpand1 to get some sense of where the error is coming from, but no luck.

9

Familiarity with CL will help, but Julia’s AST’s have a more structured representation. Direct manipulation is tricky, I usually do macros with packages like

Again, I don’t know JuMP, but I would read the docs, and then look at what a @constraint expands to, and build the expression directly without macros.

10

@Manny8888 Parse("x[1,1] * x[1,2] == 3") doesn’t work with @constraint, because it is julia expression, whereas @constraint requires JuMP expression:

m = Model()
x = @variable(m, x[1:10, 1:10])
ex = AffExpr([x[1,1], x[1,2]], [1,1], -2.0)
@constraint(m, ex == 0)

Please have a look at docs.

If You know what indices of x the variables A1 and A2 correspond to (in 3 * A1 A2), it seems that this could be easily done with a modification of the @constraint macro.

11

With further experimenting, generating JuMP expression is not an option. The parsing functions are not exported by JuMP.jl. Copying the functions into a notebook is not worth it.

I think I found a way (obvious with hindsight).

Given a constraint "20 * E2 E3"
I can generate the following string "@constraint(m, x[5,2] * x[5,3] == 20)"

Then this works: eval(parse("@constraint(m, x[5,2] * x[5,3] == 20)"))

12

If You follow the path generate string → parse → eval, then you’re doing something wrong. But since you keep your code close to chest, there is not much we can help;)

Given D a Dict{String, JuMP.Variable} (or however you translate names into variables) you can construct a constraint without parsing strings
(WARNING: this is first try crude solution cooked in 5 minutes, uses global Dict, etc, don’t use it!)

using JuMP
m = Model()
x = @variable(m, x[1:3, 1:3])
global const D = Dict{String, JuMP.Variable}(
    "A1"=> x[1,1], "A2"=> x[1,2], "A3"=> x[2,1], "A4" => x[2,2],
    "B1"=> x[1,3], "B2"=> x[2,3],
)
macro expr_str(s)
    ss = split(s)
    rhs = parse(ss[1])
    op = ss[2]
    vars = [eval(D)[v] for v in ss[3:end]]
    
    if op == "+"
        return AffExpr(vars, ones(length(vars)), -rhs)
#     elseif op = "*"
#         ...
#         return @NLexpression
    else
        throw(ArgumentError("No know constraint for operator $op"))
    end
end

ex = expr"13 + A1 A2 B1 B2"
@constraint(m, ex == 0)
1 Like
13

I’ll have detailed look at your suggestion (thanks a lot for proposing code!).

In the meantime, here is where I am currently at:


# Load the JuMP library
using Cbc
using JuMP
using MathProgBase

textProblem = """
6
13 + A1 A2 B1 B2
180 * C1 D1 D2 E1
9 + F1 F2 F3
2 = C2
20 * E2 E3
15 + A3 A4 A5
6 * B3 C3
11 + C4 D3 D4 
3 = B4
9 + D5 E4 E5 F4
2 / B5 C5 
18 + D6 E6 F5 F6
8 + A6 B6 C6
"""

problemList = split(textProblem, "\n")
problemsize = parse(problemList[1])



# Create a model
m = Model()

# Create the binary variables
@variable(m, x[1:problemsize, 1:problemsize, 1:problemsize], Bin)

# For each cell, calculate the value in that cell
@variable(m, v[1:problemsize, 1:problemsize], Int)

for i = 1:problemsize
    for j = 1:problemsize
        @constraint(m, v[i, j] == sum( (x[i, j, k] * k) for k=1:problemsize))
    end
end
            

for i = 1:problemsize, j = 1:problemsize 
    @constraint(m, sum(x[i,j,k] for k=1:problemsize) == 1)
end

for row_or_col = 1:problemsize  # Each row, OR each column
    for digit = 1:problemsize  # Each digit
        
        # Sum across columns (j) - row constraint
        @constraint(m, sum(x[row_or_col, j,          digit] for j=1:problemsize )  == 1)
        
        # Sum across rows (i) - column constraint
        @constraint(m, sum(x[i,          row_or_col, digit] for i=1:problemsize)  == 1)
    end
end

function A1_to_index(a1::String)
    c = string(a1[1] - 'A' + 1)
    r = a1[2]
    
    return "v[" * c * "," * r * "]"
end

# Looping through all the constraints

counterBinary = 0
counterMult   = 0
listExprs = []
for i = 2:length(problemList)-1
   
    # The current constraint is parsed into total of the operation and the operation
    constraintText = split(problemList[i])
    constraintValue = constraintText[1]
    constraintOp = constraintText[2]
    constraintCells = map(x -> A1_to_index(convert(String, x)), constraintText[3:length(constraintText)])
    
    cc = ""
    if (constraintOp == "+") || (constraintOp == "=")
        cc = join(constraintCells, " + ") * " == " * string(constraintValue)
        push!(listExprs, "@constraint(m, " * cc * ")")
    
    elseif constraintOp == "*" 
        counterMult += 1
        multVariable1 = "mult" * string(counterMult)
        push!(listExprs, 
                "@variable(m, " * multVariable1 * ", Int)")
        cc = constraintCells[1] * " * " * constraintCells[2] * " - " *
                multVariable1 * " == 0"
        push!(listExprs, "@constraint(m, " * cc * ")")
        println(cc)
        
        if length(constraintCells) > 2
            for j = 3:length(constraintCells)
                counterMult += 1
                multVariable2 = "mult" * string(counterMult)
                push!(listExprs, 
                        "@variable(m, " * multVariable2 * ", Int)")
                cc = multVariable1 * " * " * constraintCells[j] * " - " *
                        multVariable2 * " == 0"
                push!(listExprs, "@constraint(m, " * cc * ")")
                multVariable1 = multVariable2
                println(cc)
            end
        end
        
    elseif constraintOp == "-"
        cc =          constraintCells[1] * " * " * constraintCells[1] * " - " * 
             "2 * " * constraintCells[1] * " * " * constraintCells[2] * " + " *
                      constraintCells[2] * " * " * constraintCells[2] * " == " * string(constraintValue)
        push!(listExprs, "@constraint(m, " * cc * ")")
        
    elseif constraintOp == "/"
        counterBinary += 1
        binvariable1 = "bin" * string(counterBinary)
        push!(listExprs, 
                "@variable(m, " * binvariable1 * ", Bin)")
        
        counterBinary += 1
        binvariable2 = "bin" * string(counterBinary)
        push!(listExprs, 
                "@variable(m, " * binvariable2 * ", Bin)")
        

        cc = binvariable1 * " + " * binvariable2 * " == 1 "
        push!(listExprs, "@constraint(m, " * cc * ")")
        println(cc)
        
        cc = binvariable1            * " * " * constraintCells[1] * " - " * 
             string(constraintValue) * " * " * constraintCells[2] * " == 0" 
        push!(listExprs, "@constraint(m, " * cc * ")")
        println(cc)
        
        cc = binvariable2            * " * " * constraintCells[2] * " - " * 
             string(constraintValue) * " * " * constraintCells[1] * " == 0" 
        push!(listExprs, "@constraint(m, " * cc * ")")
    end
    
    println(cc)
end

println("")

map( x -> eval(parse(x)), listExprs)

# We are now ready to solve the problem
# For this to work, you must have an integer programming
# solver installed. If you don't, you can install one with
# Pkg.add("GLPKMathProgInterface")
# or
# Pkg.add("Cbc")

solve(m)

# Extract the values of x
x_val = getvalue(x)
# Create a matrix to store the solution
sol = zeros(Int,9,9)  # 9x9 matrix of integers
for i in 1:problemsize, j in 1:problemsize, k in 1:problemsize
    # Integer programs are solved as a series of linear programs
    # so the values might not be precisely 0 and 1. We can just
    # round them to the nearest integer to make it easier
    if round(Int, x_val[i,j,k]) == 1
        sol[i,j] = k
    end
end
# Display the solution
println(sol)