Feature/neighbourhood

[maartenflippo]

Introduce the neighbourhood interface into the search component. Accompanying is a super simple and naive RandomNeighbourhood. Right now the Neighbourhood interface has two methods: initialise and randomMove, but when we develop the search further this will need expanding (something akin to getMinObjective from fzn-oscar-cbls).

Move is also an abstract class, since there will likely be different types of moves (SwapMove, and the already included AssignMove, to name 2 examples). One thing that could use discussing is that Neighbourhood::randomMove returns a unique_ptr<Move>, since we cannot fix the move type in the return type of the randomMove method. This has the consequence that every call to randomMove allocates on the heap, which is not ideal. Alternatives that have been considered:

• Return a raw pointer, and have the move be a member of the concrete neighbourhood class. Then the randomMove could return a pointer to that member field, and the field can be reused between randomMove calls. This avoids any dynamic allocation, however, the return value of randomMove will always be the same (since it always points to the same move object).

  auto m1 = neighbourhood->randomMove();
  auto c1 = m1->cost(); // Assume copy of cost
  auto m2 = neighbourhood->randomMove();
  auto c2 = m2->cost(); // Again, copy of cost
  // m2 == m1, which might not be desirable.
  // c2 != c1, since the second call to randomMove() altered the move

• Another option that was considered is to not have Move be an abstract class. Rather, it is a class that takes something like a MoveType. In the probe and commit functions then it can switch on the move type and perform the appropriate actions. This would allow returning Move as an object rather than a pointer, and there is no need to go through the v-table. It does make the move class very hard to reason about.

I would like to hear the feedback on this. Perhaps this is something a profiling session can shed more light on as well (if the heap allocation is dwarfed by the implementation of the randomMove for example, there is little benefit to optimise this little part).

[maartenflippo]

The suggestion regarding the move is probably a good idea. We can explicitly instantiate that template for N = 1 and 2 I guess. I cannot think of moves taking more than 2 variables, and looking through fzn-oscar-cbls I do see an AssignArrayMove but it does not look used.

[GustavBjordal]

There are moves that modifies more than 2 variables like the circuit related moves like 3-opt. But I think in fzn-oscar-cbls I implement it by keeping an array of 3 moves that modifies 1 variable, rather than 1 move of 3 variables. The latter would of course be more efficient and is where we are headed here.

[GustavBjordal]

Also, yes we should indeed have some utility functions like:

Move<2> swapMove(Engine& e, VarId a, VarId b){
  return Move<2>({a,b}, {e.whateverTheFunctionForGettingValueIsCalled(a), e.whateverTheFunctionForGettingValueIsCalled(b)});
}

[maartenflippo]

I altered the implementation of Move as per your suggestion. It did require a change to the neighbourhood interface, since in the signature we do not know what the size of the move is. This problem was overcome by committing the Move inside the randomMove function.

An alternative that I explored was to have the neighbourhood interface take a template parameter N indicating the size of the move. However, this does not work well when neighbourhoods are combined, as nested neighbourhoods will likely create moves of different sizes.

[GustavBjordal]

That sounds good. I didn’t consider the impact it would have on the neighborhood interfaces. I agree with your observations and suggestions. For now let’s merge this, but I’m afraid we may have to revisit this design when you start implementing more neighborhoods and combinators.

[maartenflippo]

Right, good that you mention it. My thoughts on this are that it is probably easier to see how that would work when the search procedure is sketched out. So I can add those in a separate PR.

[GustavBjordal]

Here's one thought, Neighbourhoods don't have to return moves (to a combinator or to the heuristic), just the cost of the move and some way of reconstructing the move. Since we (will) have checkpoint as a reset mechanism, the neighbourhood can be stateful. Not sure if this is helpful though and might lead to other issues.

[frejknutarlewander]

Good work :100:. I could not find any tests for Neighbourhoods, but this can be added at a later point. I added Gustav's final comment as a task so that it is not instantly forgotten.