Procedural Nonlinear Constaint Generation - String to NLconstraint

Specific Domains Optimization (Mathematical)
, ,
1

I am implementing a large scale nonlinear program solver using the JuMP interface to IPOPT.

The Nonlinear Modeling section of JuMP v0.21.0 documentation clearly explicates that all expressions used in NLconstraint and NLobjective must be scalar operations. Nonlinear Modeling · JuMP

For this particular appreciation, manual derivation of scalar NLconstraint expressions is prohibitive due to their quantity and complexity.

As an attempt to work around this limitation, scalar nonlinear expressions were derived and delivered as strings using meta programming/symbolic math packages; The thought being that these strings could be parsed, evaluated and passed to NLconstraint. In practice this does not work.

The question is thus -

How can a string be parsed into an expression ingestible by NLconstraint/NLobjective?

With julia’s meta-programming faculty there must be a way to accomplish this without altering nonlinear modeling/autodiff source code.

The task is illustrated on the toy problem below.

Suppose the nonlinear constraint has been delivered as a string taking one of the following forms, parse it such that it may be passed to NLconstraint

“x[1]^3 + 5.0*x[1]*x[2]”

or

“x1^3 + 5.0*x1*x2”

Working Toy Problem

using JuMP
using Ipopt
m = Model(with_optimizer(Ipopt.Optimizer))
@variable(m, x[1:2])

set_lower_bound(x[1], 0.0)
set_upper_bound(x[1], 2.0)
set_lower_bound(x[2], -3000.0)
set_upper_bound(x[2], 3000.0)
@NLobjective(m, Max, 5*x[1]^2*x[2]-3*x[2]^2)
@NLconstraint(m, x[1]^3 + 5.0*x[1]*x[2] <= 3.0)
optimize!(m)

Optimal Solution

obj val: 1.5689952589360394
x[1] val: 1.0697545858077664
x[2] val: 0.3320013320392786

println("obj val: ", objective_value(m0))
println("x[1]: ", value(x[1]))
println("x[2]: ", value(x[2]))

Here are three methods which are unsuccessful in converting a string to an expression ingestible by NLconstraint

Attempt 1

m = Model(with_optimizer(Ipopt.Optimizer))
@variable(m, x[1:2])
f = eval(Meta.parse("x[1]^3 + 5.0*x[1]*x[2]"))
@NLconstraint(m, f <= 3.0)
optimize!(m)

Attempt 2

m = Model(with_optimizer(Ipopt.Optimizer))
@variable(m, x[1:2])
@NLconstraint(m, eval(Meta.parse("x[1]^3 + 5.0*x[1]*x[2]")) <= 3.0)
optimize!(m)

Attempt 3

m = Model(with_optimizer(Ipopt.Optimizer))
@variable(m, x[1:2])
function f(x1, x2) eval(Meta.parse("x1^3 + 5.0*x1*x2")) end
register(m, :my_f, 2, f, autodiff=true)
@NLconstraint(m, my_f(x[1], x[2]) <= 3.0)
optimize!(m)
1 Like
2

The relevant section of the documentation is here: Nonlinear Modeling · JuMP. You must create a Julia Expr object with the JuMP variables spliced into the expression tree. For example:

m = Model(Ipopt.Optimizer)
@variable(m, x[1:2])
# Use Meta.parse and custom transformations to create this object from a string. eval() is not needed.
expr = :($(x[1])^3 + 5.0 * $(x[1]) * $(x[2]))
add_NL_constraint(m, :($expr <= 5))

The string name of the variable is irrelevant in this setting as far as JuMP is concerned. The same code would work for anonymous variables x = @variable(m, [1:2]) that have no names.

1 Like
3

Your comment makes sense; I am now struggling with the implementation details surrounding this comment:

# Use Meta.parse and custom transformations to create this object from a string. eval() is not needed.

Could more granular guidance be offered on how to go about transforming the below string (or a similar modified string)

str = "x1^3 + 5.0*x1*x2"

into

expr = :($(x[1])^3 + 5.0 * $(x[1]) * $(x[2]))

given

m = Model(Ipopt.Optimizer)
@variable(m, x[1:2])

For example, the following results in “Unrecognized expression x[1]. JuMP variable objects and input coefficients should be spliced directly into expressions.”

str = "$(x[1])^3 + 5.0*$(x[1])*$(x[2])"
expr = Meta.parse(str)
add_NL_constraint(m, :($expr <= 3))
4 
using JuMP

substitute_args(ex, vars) = ex
substitute_args(ex::Symbol, vars) = get(vars, ex, ex)
function substitute_args(ex::Expr, vars)
    for (i, arg) in enumerate(ex.args)
        ex.args[i] = substitute_args(arg, vars)
    end
    return ex
end

model = Model()
@variable(model, x[1:2])
str = "x1^3 + 5 * x1 * x2"
ex = Meta.parse(str)
vars = Dict(:x1 => x[1], :x2 => x[2])

set_NL_objective(
    model, 
    MOI.MIN_SENSE,
    substitute_args(ex, vars)
)
2 Likes
5

The forloop makes sense as does the dictionary associating symbols in the expression with jump variables.

Would you be able to elaborate on how the function “substitute_args” works? Specifically I do not understand -

  1. Why are these two lines needed before the definition of “substitute_args”?
    “”"
    substitute_args(ex, vars) = ex
    substitute_args(ex::Symbol, vars) = get(vars, ex, ex)
    “”"
  2. How can the function “substitute_args” be called within the definition of “substitute_args”?
6

Hopefully these answer your questions:

Why are these two lines needed before the definition of “substitute_args”?

They are different methods of the same function: Methods · The Julia Language

This is a fundamentally cool feature of Julia, so it’s worth learning in detail.

How can the function “substitute_args” be called within the definition of “substitute_args”?

Most programming languages allow this. See, e.g., Recursion (computer science) - Wikipedia

2 Likes
7

Thank you for this. After taking time to digest and implement, this reply explains in full how the substitute_args function works.

Thanks you for these answers, they solve the stated problem.

8

An interesting follow on has risen from development of a unit test exercising the core functionality of substitute_args.

The expectation is that that ex_out_desired will be identical to ex_in after it is acted upon by substitute_args. Though the two expressions appear equal, the test fails per below stack trace.

What nuance am I missing that causes ex_out_desired == ex_out to evaluate to false? How could this unit test be restructured to verify that substitute_args has indeed spliced the JuMP variables into the expression tree?

Trace:

JuMP Variable Substitution: Test Failed at /home/test/substitute_args.jl:22
  Expression: ex_out_desired == ex_out
   Evaluated: s[1] + s[2] == s[1] + s[2]

Unit Test:

using Test
using JuMP

sa(ex, vars) = ex
sa(ex::Symbol, vars) = get(vars, ex, ex)
function sa(ex::Expr, vars)
    for (i, arg) in enumerate(ex.args)
        ex.args[i] = sa(arg, vars)
    end
    return ex
end

@testset "Substitute Arguments Tests" begin
    @testset "JuMP Variable Substitution" begin
        md = Model()
        @variable(md, s[1:2])

        ex_in = Meta.parse("x + y")
        ex_out_desired = :(s[1] + s[2])
        vars = Dict(:x => s[1], :y => s[2])   
        sa(ex_in, vars)
        @test ex_in == ex_out_desired

    end
end
9

You need to interpolate the variable into ex_out_desired: :($(s[1]) + $(s[2])).

You can see the expression with dump(ex_out_desired).

1 Like
10

Excellent, this worked.