Closed torressa closed 4 years ago
Excellent idea !
Another very simple example with explanations can be found here.
Just opened a new branch patch32
with some initial work. See check list above for remaining conversions
On dev branch. Closed by #39
@Kuifje02 @Halvaros Just ran the new version on the Solomon instance and comparing with the old (OLD) comp results from https://github.com/Kuifje02/vrpy/issues/8#issuecomment-612176272. We get some pretty amazing speed up! Average of over 10,000% faster and scales a lot better! Needs more testing but definitely faster
Thanks guys, great work!
As mentioned here, for the diving heuristic to work, for some speed up, it would be good to rework
master_solve_pulp.py
such that it doesn't have to be reformulated in every iteration of the column generation procedure.For a column generation friendly way of updating the constraints, one can formulate the problem by columns (seen an example).
The idea is to
pulp.LpConstraintVar
, with only the sign (<=, >=) and RHS specified.pulp.LpVariable
in already existing constraints with the appropriate coefficient, using thee
parameter. Here, one can use pulp operations likepulp.lpSum
to add variables to multiple constraints at once (this can be seen in the example)To update the constraints throughout the column generation procedure, the constraints has have to preserved. For example as a dictionary in an attribute.
Constraints Converted
Variables Converted