Skip to content
This repository has been archived by the owner on Jun 14, 2020. It is now read-only.

Lazy variables dict after delete. #97

Open
joaquimg opened this issue Mar 14, 2019 · 7 comments
Open

Lazy variables dict after delete. #97

joaquimg opened this issue Mar 14, 2019 · 7 comments

Comments

@joaquimg
Copy link
Member

Currently we have a dict mapping variables to indices.
We only actualy need that onde a variable is deleted, before deletion the variable reference already have the correct index.
By implementing this we can bring back performance of JuMP 0.18 in many parts of the code, in models that do not require deletions.

@blegat
Copy link
Member

blegat commented Mar 15, 2019

MosekTools has a special linked list to have it more efficient than a Dict when you delete variables:
https://github.com/JuliaOpt/MosekTools.jl/blob/master/src/LinkedInts.jl
This is related but it's not a priority, not using the dict when no variable has been deleted has higher priority

@ndinsmore
Copy link
Contributor

@joaquimg do you have a sense of which operations are slow right now and on which solver? Because if you apply #95, #101, jump-dev/Clp.jl#57, most of the profiling I have done seems to indicate that the Julia code is no longer the bottleneck. Atleast when using Clp

@joaquimg
Copy link
Member Author

joaquimg commented Apr 9, 2019

Clp and GLPK are much slower that Gurobi, CPLEX and Xpress.
I’d say that adding contraints is the way to test this. The require many dictionary lookups.

@blegat
Copy link
Member

blegat commented Apr 10, 2019

Why having a Dict instead of a Vector ? If variables are deleted you could just store 0 to specify that the variable index is not valid.

@joaquimg
Copy link
Member Author

Yea but then the vector would grow a lot.
The other options it to re use like mosek.

@blegat
Copy link
Member

blegat commented Apr 10, 2019

Mosek also use a vector for mapping MOI index to Mosek column. It reuses columns but not MOI index. The MOIU Model also has vectors which as large as the number of variables created (including those deleted). We should not optimize the variable deletion case too much IMO.

@joaquimg
Copy link
Member Author

I think that addition should be as fast as possible and deletion should only come after.
Deletion could be improved with batch deletion later.

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants