Very Large Problem Initial Solution Speed Up

jsprit
1

Hi there,

I’ve a problem with 50k jobs and cannot come up with any solution which would speed up initial solution search.

Steps I did:

  1. Reduce threads to 1 (Somehow it helps in some cases)
  2. Use Best Insertion (It’s faster)
  3. Use Fast Regret (Helps not waste time)

But this worked for problem with thousands jobs. But now they come up with 50k jobs and it takes aeons to just create initial solution.

I’d appreciate any help or tip what to do.

2

Hi @Tomas_Benedikt

Depending on your domain if you have some kind of domain knowledge that will allow you to set up hard activity constraints I have seen this speed up the algorithm significantly. The constraints basically say you cannot insert x activity here. Having the constraints especially if they are quite strict can significantly reduce the solution space that needs to be explored as most solutions are thrown out early and don’t need to be explored.

The one caveat of the constraints is you may get a suboptimal solution quicker because the constraints enforce something that is less optimal.

An initial though on a useful constraints would be splitting up the data into smaller sets and optimizing those for example

  • clustering the activities beforehand, optimizing the clusters, and then setting up a constraint that enforces the cluster order, i.e. all items in cluster 1 must be before all items in cluster 2 which must be before all items in cluster 3. Ff there are significantly less clusters than activities this can speed it up significantly even though it is 2 optimizations
  • A less involved version of this could be saying I know activities in set x are near the beginning, set y are near the middle and set z are near the end so add a hard constraint that activities in set x must be before activities in set y which must be before activities in set z
  • Even less involved would be using some heuristic to pick a middle activity, and split your activities in half into those that must be before the middle one and those that must be after
1 Like