odow on gh-pages
build based on f7569b6 (compare)
odow on docs
[docs] Add missing docstrings a… (compare)
Ok. I really need to polish the code and check if it really does not bug anything (I fear other methods may depend on the fact the deletions were eager and do not call update_if_needed when they should). The values are for a single (second) run with that instance (where I delete 30k variables from 50k total). You can ask me more info but the basics seem to be:
With my patch and direct_model:
Without my patch (but with direct_model too):
So... if you people can give me directions to make a full pull request and give a good testing if it does not break anything else, I would be happy. If the buffering is too clunky I may implement the delete(model, vector of variables) instead. But it would be good to me to be able to add this to the package, so I do not need to explain in my paper I had to use a patched version, XD.
@mtanneau You said before "To ensure consistence of variable/constraint indices, the wrapper will perform that update every time a variable/constraint is deleted. Hence, deleting lots of variables/constraints is slow.
There's no simple fix because of the need to ensure that the indices will remain consistent: when deleting a variable, the indices of all subsequent variables are shifted in the Gurobi object, while the MOI indices are not. Thus the MOI<-->GRB index correspondence must be updated."
I have an implementation of @odow's non-buffered suggestion (https://github.com/JuliaOpt/Gurobi.jl/compare/master...henriquebecker91:hb/simple_lazy_update) and my implementation that buffers the deletes (https://github.com/JuliaOpt/Gurobi.jl/compare/master...henriquebecker91:hb/lazy_delete). My implementation of @odow's no-buffer suggestion gives me wrong results, clearly are not the right variables that are being deleted (the warm start is not recognized, and the best estimate is wrong, giving a suboptimal solution at end). Seems to me that updating the column fields in model.variable_info without calling update on the gurobi model will desynchronize them (as you said), so a no-buffer solution is not possible because to keep the model.variable_info.column and Gurobi columns synced between calls to delete we need to update the indexes on Gurobi after each deletion (what is being done right now, with bad performance), or keep track of which column indexes were deleted since last gurobi update to correct the indexes of new deletions (what my buffered solution ends up doing).
So, it is not that @odow's suggestion has not a "good enough" performance (in my tests it had not, it took 70s, but as the code is wrong I cannot be sure the time makes sense), but I do not see how to make it correct without adding the extra complexity the buffered version already adds. I see now too that my buffered version needs some extra work, because calls to is_valid will probably give "true" for already deleted variables, if no other method forced Gurobi to update.
Unfortunately, it is far from perfect and I have no time to solve all the things it breaks. For it to work in all cases either: (1) we accept that model.variable_info and gurobi may be both outdated, and call _update_if_necessary in the beginning of basically any other method (even the ones that just query model.variable_info length or something like that, as update_if_necessary will update both model.variable_info and gurobi, not just gurobi); or (2) we accept model.variable_info and gurobi may not be synced, with model.variable_info keeping up to date with everything and gurobi may be outdated (kinda like it is currently), but there will be an extra structure to translate the "predicted column indexes" (the values they will have after the next call to update) which are inside model.variable_info to the "current column indexes" (the values used inside the Gurobi model while an update was not yet called). Anything that uses columns would need to apply this translation as last step before calling a wrapped gurobi method. Calling _update_if_necessary would clear this translating structure, and update the gurobi model, but leave model.variable_info alone (as it already has the predicted state for after the update).
It would be much simpler to JuMP to provide a delete(model, vector of variables) that atomically deletes a bunch of variables, and on Gurobi.jl implement this as a single call to del_vars and one to _update_if_necessary, and no need to save any extra state in the model. But this would need to at least create a new method in JuMP interface, providing a fallback implementation, and specializing in Gurobi to not use such fallback. I will use a workaround for now. If you people think my suggestion is worth implementing, then I can try to contribute to it, but I cannot rely on solving this the right way for now.
update_if_necessarythe corresponding function.
OTHERwhen deleting variables. Then your modifications should not have any impact. If the bug remains, then it must come from somewhere else.
update_if_necessarywith OTHER. I have noticed my last comment was not very clear. What I wanted to say was: as I gathered from my initial tests, the error happens if
updateis not called inside/after every call of delete (as in @odow's suggestion and mine too).