juliaintervals/intervalconstraintprogramming.jl

Calculate rigorously the feasible region for a set of real-valued inequalities with Julia

intervalconstraintprogramming.jl's Issues

Allow \circ for composition

Allow defining variables

E.g.

x = Variable(:x)
y = Variable(:y)

Then

x + y <= 3

becomes a constraint object.

Parametrize paving on separator

Allow reusing local variables

e.g.

a = f(a)
a = f(a)

Allow parameters in constraints

It is not clear what syntax to use to distinguish variables (that specify the dimensions of the space that the feasible region lives in) and parameters (basically, constants that are specified externally).

Maybe

S = @constraint(c, 1 <= (x - c)^2 <= 3 )

The last argument is the constraint; the others specify that those variables are parameters.
Then S(1) should be the constraint specialised with c = 1 etc.

Make GeneratedFunction object that contains function and code

Re-add expressions to contractor and define a good show method

And add a show method for the result of @function.

Bug in x*y==0

julia> X = IntervalBox(-100..100, 2)
[-100, 100] × [-100, 100]

julia> C = @constraint x*y==0
Separator:
  - variables: x, y
  - expression: x * y ∈ [0, 0]

julia> C(X)
([0, 0] × ∅, [-100, 100] × [-100, 100])

Clean up code by introducing `VariableSet` type

Treat infinite intervals specially

• Bisect them until they are finite.

• Add a check to not bisect if nextfloat(a.lo) == a.hi.

Add support for functions

Functions from n variables to 1:

@function f(x, y) = x^2 + y^2

@constraint 1 <= f(x, y) <= 3

@function f(x) = 4x*(1-x)
@constraint 0.1 <= f(f(x)) <= 0.3

Abstract separator type

Then concrete separator types:

ConstraintSeparator:

@constraint disc = x^2 + y^2 <= 1   # note position of `@constraint`

Store the name inside the type.

CombinationSeparator:
e.g. S1 \cap S4

Rewrite backward function code generation

• [ ] Generate explicit instructions instead of functions?
• Eliminate unnecessary operations for constants. Started in #72
• Do not return the variables that are unchanged.
• Move to IntervalContractors package.
• Make versions of the backward functions that take interval unions and return interval unions.

Move interval functions to ValidatedNumerics

• iseven, isodd Rewritten in #72 to not require iseven of an Interval
• bisect

Any other function that just manipulates Intervals or IntervalBoxes. There are none left.

Refactor forward and backward functions

Forward should take as argument an IntervalBox, and return an IntervalBox that is the output, together with a tuple of the intermediate variables.

Backward should take as argument an IntervalBox and the tuple, and return an IntervalBox.

Contractor should be parametric on the size of the IntervalBoxes it takes, and forward and backward should type annotate the sizes of the tuples.

Unroll for loops

Like

for i = 1:10
    a = f(a)
end

Add support for iterating functions

f(f(x))

This should be doable just using the separator for f?

Make a version of separator that leaves the interval as a variable?

Move reverse-mode functions to new package

Replace parsing with Espresso.jl!

Triple intersection of separators not working

Implement binary tree for pavings

Allow parameters in constraints

Syntax as in #8.
These should probably become extra arguments of the contractor / separator functions.

Allow pave for a Vector of separators

Assume intersection by default.

Use generated functions for * for Volume

julia> immutable Vol{N}
       volume::Float64
       end

julia> import Base.*

Instead of

julia> *{N1,N2}(V1::Vol{N1}, V2::Vol{N2}) = Vol{N1+N2}(V1.volume * V2.volume)
* (generic function with 150 methods)

use

@generated *{N1,N2}(V1::Vol{N1}, V2::Vol{N2}) = :(Vol{$(N1+N2)}(V1.volume * V2.volume))

Add simple multi-dimensional root finder using bisection

From this notebook

Use fast powers by default

Rewrite Contractor as normal function

Assignment of tuples

(a, b) = f(x, y)

Efficient version of separator

That does not duplicate contractor.

Add support for ≤ etc.

Swap out and in in sepators?

To be consistent with Luc Jaulin's papers.

Allow creating constraint (separator) from contractor and region

Or contractor and contractor!

power_rev incorrect for odd powers

julia> b
[-1.00001e+16, 1]

julia> x
[-1e+08, 1e+08]

julia> IntervalConstraintProgramming.power_rev(b, x, 3)
([-1.00001e+16, 1],[0, 1],[3, 3])

Add higher-dimensional functions

In particular, allow iterating them.

Change name of internal variables

To minimize name clashes, e.g. __z1

Mangle local variable names in functions

E.g.
@function f(x) = (a = x^2; a+y)
The a should be uniqued at the moment of generating code (outside the function).

Use 2-tuple for children of a node

Mark non-existent child with sentinel value -1.

Backward functions as inverses

inv(::typeof(+)) = …

Call with
inv(+)(...)

pave is broken

On 0.2 and master; reported by @kriukov.

Add show method for @function

Done in #78.

Bikeshed name for set_inversion

• setinverse
• inv
• domain
• solve
• preimage
• feasibleset
• feasibleregion
• feasible

Re-implement Sigma.jl

https://github.com/zenna/Sigma.jl

Backward functions that return interval unions

Make versions of the backward functions that take interval unions and return interval unions.

Rewrite reverse-mode functions

So that they operate on a single variable. Move these to ValidatedNumerics.jl.
Make sure to use notation consistent with the IEEE standard 1788-2015.
(This specifies a specific, to my mind strange, order for the arguments.)

Rename backward functions

Eg +_inv

Rename `vol` -> `Vol`

There is no need to have different names.

Add type for output of setinverse

Maybe called Paving

Allow unary minus

Reduce number of `begin` in code generation

Allow expressions of the form `y == exp(x)`

Instead of y - exp(x) == 0