by

Where communities thrive


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

    mlubin on gh-pages

    build based on 9bf82e9 (compare)

  • 09:33

    blegat on master

    Update aff_expr.jl (#2342) Rem… (compare)

  • 09:33
    blegat closed #2342
  • 02:50
    odow synchronize #2341
  • 02:50

    odow on fix_linearity

    Use USER_OPERATOR_ID_START inst… (compare)

  • Sep 21 23:56
    vtjeng commented #2342
  • Sep 21 23:28
    mlubin commented #2342
  • Sep 21 21:40

    mlubin on gh-pages

    build based on b5acc79 (compare)

  • Sep 21 21:18

    blegat on master

    Fix StackOverflow for NestedIte… (compare)

  • Sep 21 21:18
    blegat closed #2336
  • Sep 21 21:18
    blegat closed #2335
  • Sep 21 19:54
    vtjeng opened #2342
  • Sep 21 08:00
    blegat closed #1165
  • Sep 21 08:00
    blegat commented #1165
  • Sep 21 04:25
    odow opened #2341
  • Sep 21 04:24

    odow on fix_linearity

    Fix linearity check of user-def… (compare)

  • Sep 21 04:22
    odow assigned #2340
  • Sep 21 02:07
    odow edited #2340
  • Sep 21 02:06
    odow labeled #2340
  • Sep 21 02:06
    odow opened #2340
Henrique Becker
@henriquebecker91
I am using Gurobi 0.7.2 and JuMP 0.20.0 and deleted about 30k variables from a model with 50k variables and it took many minutes to do so (much more than creating/solving the model, and after deleting there was a message: "Warning: excessive time spent in model updates. Consider calling update less frequently."). I see that a similar problem was already dealt with in the recent past: JuliaOpt/Gurobi.jl#216, are these changes already included in the last version? Or there is a version to be launched that solve them? Should I open a issue? If the issue is not too deep I may try to contribute.
Oscar Dowson
@odow
Deleting variables and constraints is slow and hard to fix. Why do you want to delete so many?
BridgingBot
@GitterIRCbot
[slack] <ExpandingMan> hello all, any chance of getting an 0.20.1 release to fix the sparse matrix issues in Julia 1.3?
mtanneau
@mtanneau
@henriquebecker91 Gurobi updates models in a lazy fashion. That means all modifications are buffered until an update function is called.
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.
Henrique Becker
@henriquebecker91

@odow I am reproducing and improving over the method presented in a paper (https://pubsonline.informs.org/doi/abs/10.1287/ijoc.2016.0710) it involves a "final pricing" which is done after solving the continuous relaxation, and if done right, should remove 40~70% of the variables, making the model considerably easier to solve. The authors have lost their code (one of the reasons I am re-implementing it in Julia), but by their description the deletion was done the same way I am trying to do it.

@mtanneau hmm, are you saying that JuMP is eager by default (and should stay this way)? or that was too much work and nobody implemented a lazy layer inside the wrapper that keeps an index correspondence table and only updates when optimize is called? seems to me that this kinda throws away the utility of using JuMP over a solver with lazy update semantics.

I will try to find a workaround for the time being. Probably I will need to create the model again, without the variables, and copy what I can from the old model, translating from the old indexes to the new ones.

Miles Lubin
@mlubin
FYI we are transferring juliaopt.org from a private account to NumFOCUS today. This could involve some downtime as the DNS is reconfigured.
Robert Schwarz
@rschwarz
@henriquebecker91 Instead of removing the variables on the JuMP side, could you instead fix them to 0 (or some lower bound)? Then the Gurobi would be able to remove all of these variables in presolve, but on the JuMP-side, the indices remain valid.
I understand (from reading the comments above) that adding variables and constraints to Gurobi is lazy, but removing variables is eager, or else one might end up in an inconsistent state.
Miles Lubin
@mlubin

by their description the deletion was done the same way I am trying to do it

Was it done using the Gurobi C API or the C++/Python API? The C++/Python APIs provide references that aren't invalidated when you delete variables. When deleting a variable in the C API, it potentially invalidates all previous indices.

Oscar Dowson
@odow
There is definitely room for improvement in how we manage the lazy updating. It would involve more caching on the Julia side, and you would have to think through different sequences of actions. For example, if you've just deleted a variable, we require an update before you can add one, or query something about the model state, since if we don't update, Gurobi will return information from the un-updated model. However, if you delete a variable, we probably don't need to update if the previous operation was also deleting a variable.
The work-around is probably to use JuMP in manual mode, which isn't documented very well. Build a JuMP model, attach the solver and solve. Then detach, make a lot of changes, like deleting variables. Then re-attach and solve again
It also looks like the paper used CPLEX, which doesn't have the same lazy updating semantics
Henrique Becker
@henriquebecker91
Yes. But CPLEX is not working with JuMP 0.20, and I need JuMP 0.20 for using the warm start methods that are present only in it.
So instead of implementing the whole thing again using CPLEX without JuMP, I decided to keep the JuMP and use Gurobi below.
I mean, I could use JuMP 0.19 + CPLEX.jl 0.5 and write for myself a warm start method that uses the underlying solver object, but I do not know how hard that would be.
Oscar Dowson
@odow
@jd-lara and I are going to look at updating CPLEX.jl next week
Henrique Becker
@henriquebecker91

@rschwarz This is a good idea, if I can trust Gurobi to do so. I will check for flags to make presolve as aggressive as possible, and run some tests to see if the presolve reduce the number of variables by the expected amount.

@mlubin See what I answered to odow, the paper uses CPLEX, but I cannot use CPLEX+JuMP and warmstart the variables, what is also necessary for the method.

@odow I will try what you propose (direct method) and compare with @rschwarz idea of fixing the variables. This kind of lazy update is something I would like to contribute to, but I am not sure if I have the time for contributing for something that needs more than a whole day of work now.

Henrique Becker
@henriquebecker91
@odow, updating CPLEX.jl would kinda solve all my headaches, but I have experiments to run and a paper to write, how much work do you think it is? I could contribute with one or two days of work, if it meant this would be solved next week. This would save me from testing workarounds, and give me a more solid paper, I just cannot delay my work too much, nor I am very knowlegeable in MOI internals, is something a beginner can help, or would take more work from you to babysit me than to your solve the problem alone?
mtanneau
@mtanneau

If you create a Gurobi model, then add (scalar) variables x, y, z, their respective indices are 1, 2, 3 (or maybe they start at 0, not sure, anyway...).
Delete variable y, and now the indices of x, z are 1, 2, which means to query the value of z you must query the value of the variable whose index is 2.
Gurobi only ever works with variable indices (unless you're using names but that's much slower), which means that you, as a Gurobi user, must keep track of which index corresponds to which variable, otherwise things go wrong.

In JuMP/MOI, if you create variables x, y, z, you get three objects x, y, and z, for which you can query whatever you want.
Delete y from the model, and the JuMP/MOI convention is that x, zstill allow you to access information about the corresponding variables, without having to make any modification to the objects x, z themselves. That means, the shift of index must be accounted for somehow. If you're using Gurobi directly, you're responsible for it. If you're using JuMP/MOI, then MOI is responsible for it.

Henrique Becker
@henriquebecker91
@mtanneau Yes, but something like @odow mentioned is possible, right? When you ask JuMP to delete a variable, JuMP does not really needs to delete a variable, it may just mark the variable as to-be-deleted in an internal structure, and everything that would need to query solver state flush this internal structure before doing what they would do. Basically, making JuMP to also have lazy updates, because being eager if a solver is lazy is problem, but being lazy if a solver is eager often is not a problem.
mtanneau
@mtanneau
@odow, is there such a thing as deleting several variables/constraints simultaneously, i.e., MOI.delete(model, x::Vector{MOI.VariableIndex})? (without using an individual delete fallback)
If so, it may be possible (hopefully without requiring to much work) to wrap GRBdelvars so that all variables are eliminated in bulk, thus resulting in a single update.
Just an idea, I haven't looked at how it would impact the re-building of wrapper-level data structures.
mtanneau
@mtanneau

JuMP does not really needs to delete a variable, it may just mark the variable as to-be-deleted in an internal structure

This is kind-of already implemented in the MOI wrapper of Gurobi: there is a needs_update flag that is updated when modifying the model.
What @odow suggested was to be less conservative as to when updates should be performed, and when not.
If you delete x, you don't need to update before deleting y. But if you add a constraint c, then you need to update before deleting y. However that requires extensive tracking of what's the stack of buffered modifications, and do I need to flush before performing some modification X. Sorting all this out is not impossible, it's just cumbersome (and someone has to do it and then maintain it)...

Oscar Dowson
@odow

how much work do you think it is?

It's a non-trivial amount of work.

It's probably not that much work to implement a "last operation was deletion" flag in the Gurobi wrapper, since this is the most expensive operation.

Miles Lubin
@mlubin
The juliaopt.org transfer is complete. Please let me know if anyone runs into trouble accessing the site.
Henrique Becker
@henriquebecker91
@mtanneau, @odow, so, if I submit a pull request to change MOI.delete of Gurobi.jl (https://github.com/JuliaOpt/Gurobi.jl/blob/master/src/MOI_wrapper.jl#L448) to always add the deletion to a queue, and add a new method to be called below _update_if_needed (called _flush_var_deletes) in all methods except delete, do you think it could be accepted? The del_vars! is already wrapped (https://github.com/JuliaOpt/Gurobi.jl/blob/2ba66a47a19050cca16f719eb1735a5620bb535a/src/grb_vars.jl#L125). I do not want to start at this if you people think it is a bad idea, but seems the best way to conciliate my needs and helping the project.
Oscar Dowson
@odow

It might be better to modify _require_update so that it is extensible to other operations:

@enum(MutatingOperation, VARIABLE_DELETION, OTHER)

function _require_update(
    model::Optimizer,
    operation::MutatingOperation = OTHER
)
    model.needs_update = true
    # You will need to add .last_mutating_operation to Optimizer
    model.last_mutating_operation = operation
    return
end

function _update_if_necessary(
    model::Optimizer, 
    operation::MutatingOperation = OTHER
)
    if model.last_mutating_operation == operation == VARIABLE_DELETION
        # If the last operation was a variable deletion and this one is too,
        # we can safely delay the update.
    elseif model.needs_update
        update_model!(model.inner)
        model.needs_update = false
    end
    return
end

And then edit the MOI.delete function to pass VARIABLE_DELETION as the optional argument.

Does that make sense?

Henrique Becker
@henriquebecker91
Yes, it makes sense. I need to change update_model! to do all deletions if it is the case, right? Will start working on it now.
Oscar Dowson
@odow
I think you just need to update _require_update. and _update_if_necessary here: https://github.com/JuliaOpt/Gurobi.jl/blob/4bc1f91a398fd149c3c0c0fdb4288a5b08b46957/src/MOI_wrapper.jl#L449-L452
You don't need to change update_model!.
Henrique Becker
@henriquebecker91
Oh, ok, you intend to keep calling del_vars! over a single var, and then executing the loop over all variables each time. I was thinking of keeping the variables in a vector and then deleting them all with a single call to del_vars! and making a single sweep to correct the indexes.
I can do it in this simplified way you suggest, but if you think I am not adding too much complexity, I would prefer to buffer them for maximum performance.
Miles Lubin
@mlubin
What if someone alternates between deleting constraints and deleting variables?
Henrique Becker
@henriquebecker91
@mlubin In this case it will revert to bad performance we have now, independently if it is implemented as @odow suggested or how I have suggested. Ok, the way I have suggested will be slight worse because it will push! and pop! a vector too, but basically, both ways are just for optimizing multiple variable deletions in sequence. My way adds more code complexity but is more efficient when this happens (lots of variables are deleted in sequence).
Henrique Becker
@henriquebecker91
@mlubin As @mtanneau said, the problem is cumbersome. Making deleting constraints and variables alternately efficient is possible, but it would need to someone verify with much care what needs to be buffered and what not. In the other hand, the MutatingOperator framework that @odow suggested makes very simple to improve the performance of the same operation being called over multiple times in sequence.
Miles Lubin
@mlubin
I'd at least recommend describing the performance characteristics of the interface in the Gurobi.jl readme. It shouldn't be necessary to look at the source to know how to efficiently structure your code.
Henrique Becker
@henriquebecker91
It is a good idea. However, I have the sensation that if JuMP allowed for a specialized delete(model, vector of variable references) it would be intuitive that you have better (or the same, but never worse) performance if you call the specialized method for doing a chunk of work in a single go, than multiple repeated calls to the method that deals with one variable at a time.
Henrique Becker
@henriquebecker91
I am starting to suspect that the culprit of the bad performance is in fact CleverDict. There is a reason for it to use OrderedCollections? OrderedCollections code is seven years old and deprecated in favor of DataStructures.jl.
Oscar Dowson
@odow
You're probably looking at a different ordered collections://github.com/JuliaCollections/OrderedCollections.jl
Henrique Becker
@henriquebecker91
Yes, I was thinking of this one: https://github.com/peter1000/OrderedCollections.jl
Benoît Legat
@blegat

JuMP allowed for a specialized delete(model, vector of variable references)

You mean an easy way to do MOI.delete(backend(model), index.(var_refs)) ?

Henrique Becker
@henriquebecker91
@blegat There is a MOI.delete(Optimizer, array of var_refs)? The only one I found (in Gurobi MOI wrapper) is https://github.com/JuliaOpt/Gurobi.jl/blob/master/src/MOI_wrapper.jl#L448. But, yes, something like that, I suppose if you call what you suggested directly the JuMP model will become desynchonized with the state of the underlying solver, so JuMP would need to wrap that too, no?
Benoît Legat
@blegat

I suppose if you call what you suggested directly the JuMP model will become desynchonized with the state of the underlying solver

No, they will stay in sync. As Gurobi does not implement deletion of vector of variables, it will just fallback to deleting them one by one for Gurobi. Adding the method for Gurobi would make sense

Henrique Becker
@henriquebecker91
Good to know, maybe I will give a look at that too then, seems simple to provide such method for Gurobi MOI Wrapper, as the CCall to be used is already wrapped. I just want to finish my hunt for the reason of the bad performance deleting multiple variables in sequence. I have changed the MOI delete to just add the deleted variables in an array, and the deletion only occurs when any other method call update_if_needed, but the method continue to be slow.
Benoît Legat
@blegat
JuMP v0.20.1 will not be automatically be merged because: The following dependencies do not have a compat entry that has an upper bound: DataStructures, Calculus, NaNMath
Maybe we should add upper bounds
Miles Lubin
@mlubin
I don't see any reason not to add upper bounds.
Benoît Legat
@blegat
They might break their API which might break JuMP if we don't have any upper bound
Miles Lubin
@mlubin
Right
Benoît Legat
@blegat
Looking at DataStructures, they make a breaking release every 3-4 months we would force us to make a patch release with the same pace