Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Activity
  • 14:14

    mforets on gh-pages

    build based on 2821073a (compare)

  • 14:13
    schillic labeled #1776
  • 14:13
    schillic labeled #1776
  • 14:13
    schillic opened #1776
  • 13:58
    schillic labeled #1775
  • 13:58
    mforets opened #1775
  • 13:56
    mforets commented #1169
  • 13:56
    mforets commented #1169
  • 13:56
    mforets closed #1169
  • 13:56
    mforets commented #1169
  • 13:50
    schillic edited #1169
  • 13:40
    mforets synchronize #1774
  • 13:40

    mforets on 1250

    solve problem with sparse gener… use AbstractMatrix in cross_pro… (compare)

  • 13:38
    IssueHuntBot commented #1772
  • 13:38
    mforets updated the wiki
  • 13:37

    mforets on 1772

    (compare)

  • 13:37

    mforets on master

    #1772 - NaNs in constraints lis… (compare)

  • 13:37
    mforets closed #1773
  • 13:37
    mforets closed #1772
  • 12:56
    s0vereign starred JuliaReach/Reachability.jl
Christian Schilling
@schillic
but then in the second iteration you will have an HPolytope and have to use the slower methods
but that happens automatically
ueliwechsler
@ueliwechsler
I most cases, I would use the BallInf, but in general, I'd like to know the computational complexity of the general case, which for me is HPolytope.
Christian Schilling
@schillic
ok sure
ueliwechsler
@ueliwechsler
Thanks for the clarification, I was sloppy while dealing with the concrete types
Christian Schilling
@schillic
no problem, it gave us the opportunity to help :)
i can have a look at JuliaReach/LazySets.jl#1500 (the linear map) in the next days, but if you are eager, you can just add this option yourself and see if it helps (here)
this has a nasty tail, so you have to pass the option through several helper functions :)
basically make this line optional
ueliwechsler
@ueliwechsler
👍 thanks, I will try it out. I am curious how much it will change the performance.
Marcelo Forets
@mforets
minkowski_difference for hyperrectangular sets can be specialized as well or not?
Marcelo Forets
@mforets
But it is cheap anyways give 2 ballinf as you said above..
The equality check can also be improved..? Save half the evaluations in the dual inclusion by checking approximate equality of the support functions
Christian Schilling
@schillic

minkowski_difference for hyperrectangular sets can be specialized as well or not?

maybe, but the hyperrectangle will definitely be destroyed by the linear_map
but that would be an alternative to my other suggestion: overapproximate the result of linear_map by a hyperrectangle. hyperrectangles are closed under intersection, so this would give you a "stable" loop. and all of these operations are cheap, so i would really give it a try, just to see the potential performance boost

@ueliwechsler: can you try out the variant of your algorithm with this change?
𝒫⁺ = intersection(overapproximate(linear_map(S_inv, minkowski_difference(𝒫,𝒲)), Hyperrectangle), 𝒟)

The equality check can also be improved..? Save half the evaluations in the dual inclusion by checking approximate equality of the support functions

i didn't understand this proposal. but yeah, if typically one of the two inclusions fails, it is more efficient to do that check first (because it usually avoids the second check). and again for hyperrectangles this equality check can be made very efficient

Benoît Legat
@blegat
@mforets The advantage of JuMP is that it will automatically add needed caching and bridges layers
Christian Schilling
@schillic

@blegat while you are here: i cannot get MOI to work with Rationals. what is wrong here?

using GLPK, MathOptInterface
const MOI = MathOptInterface
N = Rational{Int}
solver = GLPK.Optimizer(method=GLPK.EXACT)
x = MOI.add_variables(solver, 1)
MOI.set(solver, MOI.ObjectiveSense(), MOI.FEASIBILITY_SENSE)
a = MOI.ScalarAffineFunction(MOI.ScalarAffineTerm.(N[1], x), N(0))
b = MOI.LessThan(N(0))
MOI.add_constraint(solver, a, b)

this throws an error:

ERROR: MathOptInterface.UnsupportedConstraint{MathOptInterface.ScalarAffineFunction{Rational{Int64}},MathOptInterface.LessThan{Rational{Int64}}}: `MathOptInterface.ScalarAffineFunction{Rational{Int64}}`-in-`MathOptInterface.LessThan{Rational{Int64}}` constraint is not supported by the model.

note that for N = Float64 this works

this is the LP (no objective) s.t. x <= 0
Christian Schilling
@schillic
hm, it seems that GLPK does not support adding Rational constraints at all
this is the method for Float64, but there is no method for other types
Christian Schilling
@schillic
(to support the theory, Float32 gives the same error)
Christian Schilling
@schillic
@mforets: i think the LP solvers only support Float64 (i updated my comment JuliaReach/LazySets.jl#1701). we should discuss how to proceed. one way is to convert from N to Float64, solve the LP, then convert back to N (which obviously has soundness issues, but it may be better than crashing; maybe there should be an option to print a warning or error)
Marcelo Forets
@mforets
I recall some threads about numeric types in MOI and JuMP. IMO LazySets should not make conversions of the result; if it doesnt qorm it doesnt slen
Doesnt work
In verimag some people used PPL, a library for polyhedra with exact coordinates
Christian Schilling
@schillic
i think we get into lots of trouble if the result changes the type
but ok
but are you fine with conversion to Float64 before calling the solver?
or should we just crash and say that we only support Float64?
i'm fine with either choice because we anyway always used Float64 so far
and it is somewhat cleaner to not do conversions
I recall some threads about numeric types in MOI
yes, MOI is ready for that. it only crashes when i pass the model to a solver
Marcelo Forets
@mforets
So the best thing may be to not do anything..
Christian Schilling
@schillic
ok but then i need to remove many Rational tests
just to say
i agree with you :+1:
can you confirm?
i think the code should work if the solver supported it
should we print a warning whenever a user tries to set up an LP with non-Float64? because the error is quite cryptic. the downside is that if the user employs a solver that supports the type, then the warning is "wrong"
Marcelo Forets
@mforets
yes, i agree about removing Rational tests which are not "consistent"
Christian Schilling
@schillic
:+1:
Marcelo Forets
@mforets
do you have an example?
Christian Schilling
@schillic
i already did it :D
Marcelo Forets
@mforets
ok
Christian Schilling
@schillic
well, every example where we called the LP solver
Marcelo Forets
@mforets
hmm not sure that i follow
Christian Schilling
@schillic
(the same holds for Float32)