Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Derive implicit constraints from input #648

Closed
jcoupey opened this issue Jan 11, 2022 · 0 comments · Fixed by #693
Closed

Derive implicit constraints from input #648

jcoupey opened this issue Jan 11, 2022 · 0 comments · Fixed by #693
Assignees
Milestone

Comments

@jcoupey
Copy link
Collaborator

jcoupey commented Jan 11, 2022

Rationale: in a typical situation with TW or capacity constraints, there are implicit max_tasks values existing for all vehicles. Say for example a vehicle has "capacity": [50] and all jobs have "delivery": [5] (or more), then this vehicle won't ever have a route with more than 10 jobs in it.

Though explicitly providing "max_tasks": 10 does not change the problem model (and solution), it does have a significant impact on computing time. Indeed, any move that would result in a route over 10 jobs for this vehicle is now discarded without even looking up its potential cost and ending up noticing it's invalid anyway. Actually the C++ object for the local search operator is not even created.

It feels weird to have equivalent models (with or without max_tasks) resulting in significantly different computing times for the exact same solution. It's also not satisfactory to require users to provide additional constraints for a reason that is tightly coupled with the internal solving process, not to mention that coming up with the right limits may not always be trivial in the first place.

So we should setup a way to derive those implicit constraints automatically and lower max tasks values accordingly for vehicles. Also, this is a great opportunity to speed up things for instances that naturally contain strong implicit constraints.

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

Successfully merging a pull request may close this issue.

1 participant