The method JuMP classifies linear/affine/quadratic/nonlinear... types of constraints

Specific Domains Optimization (Mathematical)
1

I am learning to use Julia optimization package and found that JuMP can identify the above types of constraints from the input constraint expression, I do not quite understand how JuMP does it since I haven’t located the source code related to this functionality, does it involve recursions to parse the expression to the bottom?

Thank you

2

JuMP builds up expressions by construction. It doesn’t build a generic expression and then try to detect whether it is linear or quadratic after the fact.

One approach uses operator overloading, so there are a bunch of rules like x::VariableRef + y::VariableRef produces an AffExpr:

The macros do something similar, just with slightly different calls.

If you’re just learning to use JuMP, I wouldn’t worry about this. You shouldn’t need to know any of the details.

3

Thank you,

Can I ask what you mean by “construction”, do you mean based on the expression from the macro input to construct another expression for the constraint? I saw there are basic elements like scalar affine terms, but I assume the original expression still needs to be parsed for these basic elements be correctly identified (e.g. from a mathematically complex constraint)?

1 Like
4

By construction, I mean operator overloading.

At each step, JuMP constructs an object that has a concrete type, like VariableRef, AffExpr, or QuadExpr.

We don’t look at the full expression graph and then try to tell whether the final result will be linear or quadratic.

Take this example:

julia> model = Model();

julia> @variable(model, x);

julia> f = (1 + x + 2 * x) * x
3 x² + x

is equivalent to

julia> a = 1       # ::Int
1

julia> b = a + x   # +(::Int, ::VariableRef)   --> AffExpr
x + 1

julia> c = 2 * x   # *(::Int, ::AffExpr)       --> AffExpr
2 x

julia> d = b + c   # +(::AffExpr, ::AffExpr)   --> AffExpr
3 x + 1

julia> e = d * x   # *(::AffExpr, VariableRef) --> QuadExpr
3 x² + x

The downside of operator overloading is that it creates lots of temporary objects (the b, c, and d variables). The JuMP macros do something similar to operator overloading, except that they use the MutableArithmetics.jl package to avoid creating the temporary objects.

1 Like