LocalSearch phase moveSelector clarification

[Yan Shou]

Dear all,

I am currently using optaplanner on a variant of task assignment problem, and am unclear about how default moves work for local search algorithms like Hill Climbing, Tabu Search.

Right now when my solver enters local search phase, say Tabu Search, it will generate 1000 random moves like changes or swaps that assign tasks to different employees. These moves seem to be completely randomly selected. For human operators that assign jobs to employees, they tend to move the entities that break hard constraints so that they can find other employees that assigning this task won't break hard constraints. Is this kind of logic being considered during the local search phase's default moveSelector? For Tabu Search, are the 1000 moves chosen according to their score indictment level? For Construction Heuristics, entities can be assigned according to their strength level using strongest fit or weakest fit. For Local Search, since detailed score constraint matched total list can be access for each solution, isn't indictment heat also indication of the urgency of moving the entity?

On a side note, I have business rules that must be followed for hard/medium/soft constraints, but these rules translate into score constraints that sometimes require moving multiple planning entities to get hard score reduced by 1. I understand pillar moves will be helpful for this case, but as the problem grows more complex to satisfy business needs, I find it increasingly frustrating to balance between my design of scoring constraints and my algorithms' phases' details like moveSector. What are some tips that you guys use to explore a not-so-well defined problem? It feels like I'm shooting in the dark.

I apologize if I am misunderstanding the concepts of local search or have missed parts in optaplanner's excellently written document. If I could get some pointers on where to look for examples, clarifications on above mentioned questions, I would much appreciate it.

Best regards,

Yan Shou

[Geoffrey De Smet]

With kind regards,
Geoffrey De Smet

On 19/11/2019 11:34, Yan Shou wrote:

Dear all,

I am currently using optaplanner on a variant of task assignment problem, and am unclear about how default moves work for local search algorithms like Hill Climbing, Tabu Search.

Right now when my solver enters local search phase, say Tabu Search, it will generate 1000 random moves like changes or swaps that assign tasks to different employees. These moves seem to be completely randomly selected. For human operators that assign jobs to employees, they tend to move the entities that break hard constraints so that they can find other employees that assigning this task won't break hard constraints. Is this kind of logic being considered during the local search phase's default moveSelector?

It is not considered in the default moveSelector.
What you're referring to is called "Guided Local Search" (GLS).

I have a prototype implementation of GLS, shelved on my laptop, which indeed uses the indictements to focus on the most indicted entities first. It's intresting.

The paradox is that GLS doesn't do so well on the use cases I benchmarked, as it doesn't have enough diversification (or it isn't polished enough yet). Mileage depends on the use case probably.
OptaPlanner will have GLS as part of it's arsenal in the future,
but currently we have other priorities (constrainstreams, spring boot + quarkus).

For Tabu Search, are the 1000 moves chosen according to their score indictment level? For Construction Heuristics, entities can be assigned according to their strength level using strongest fit or weakest fit. For Local Search, since detailed score constraint matched total list can be access for each solution, isn't indictment heat also indication of the urgency of moving the entity?

That is the GLS philosophy indeed, which is great for intensification.
But a good metaheuristic mixes intensification and diversification.

On a side note, I have business rules that must be followed for hard/medium/soft constraints, but these rules translate into score constraints that sometimes require moving multiple planning entities to get hard score reduced by 1. I understand pillar moves will be helpful for this case, but as the problem grows more complex to satisfy business needs, I find it increasingly frustrating to balance between my design of scoring constraints and my algorithms' phases' details like moveSector. What are some tips that you guys use to explore a not-so-well defined problem? It feels like I'm shooting in the dark.

I apologize if I am misunderstanding the concepts of local search or have missed parts in optaplanner's excellently written document. If I could get some pointers on where to look for examples, clarifications on above mentioned questions, I would much appreciate it.

Best regards,

Yan Shou

--
You received this message because you are subscribed to the Google Groups "OptaPlanner development" group.
To unsubscribe from this group and stop receiving emails from it, send an email to optaplanner-d...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/optaplanner-dev/76ac7ac9-7bb9-43a1-b3c6-b7b40bc3891d%40googlegroups.com.