Custom moves

Instead of using the generic Moves (such as ChangeMove) you can also implement your own Move. Generic and custom MoveSelectors can be combined as desired.

A custom Move can be tailored to work to the advantage of your constraints. For example, in examination scheduling, changing the period of an exam A would also change the period of all the other exams that need to coincide with exam A.

A custom Move is far more work to implement and much harder to avoid bugs than a generic Move. After implementing a custom Move, turn on environmentMode TRACED_FULL_ASSERT to check for score corruptions.

For information on the Move interface, check out the Move Anatomy section of the Neighborhoods chapter. Even though Neighborhoods is an entirely different mechanism than move selectors, they share the Move interface and therefore the same custom Move can be used in both mechanisms.

1. Generating custom moves

Now, let’s generate instances of this custom Move class. There are 2 ways:

1.1. MoveListFactory: the easy way to generate custom moves

The easiest way to generate custom moves is by implementing the interface MoveListFactory:

public interface MoveListFactory<Solution_> {

    List<Move> createMoveList(Solution_ solution);

}

Simple configuration (which can be nested in a unionMoveSelector just like any other MoveSelector):

    <moveListFactory>
      <moveListFactoryClass>...MyMoveFactory</moveListFactoryClass>
    </moveListFactory>

Advanced configuration:

    <moveListFactory>
      ... <!-- Normal moveSelector properties -->
      <moveListFactoryClass>...MyMoveFactory</moveListFactoryClass>
      <moveListFactoryCustomProperties>
        ...<!-- Custom properties -->
      </moveListFactoryCustomProperties>
    </moveListFactory>

Because the MoveListFactory generates all moves at once in a List<Move>, it does not support cacheType JUST_IN_TIME. Therefore, moveListFactory uses cacheType STEP by default and it scales badly.

To configure values of a MoveListFactory dynamically in the solver configuration (so the Benchmarker can tweak those parameters), add the moveListFactoryCustomProperties element and use custom properties.

A custom MoveListFactory implementation must ensure that it does not move pinned entities.

1.2. MoveIteratorFactory: generate Custom moves just in time

Use this advanced form to generate custom moves Just In Time by implementing the MoveIteratorFactory interface:

public interface MoveIteratorFactory<Solution_> {

    long getSize(ScoreDirector<Solution_> scoreDirector);

    Iterator<Move> createOriginalMoveIterator(ScoreDirector<Solution_> scoreDirector);

    Iterator<Move> createRandomMoveIterator(ScoreDirector<Solution_> scoreDirector, Random workingRandom);

}

The getSize() method must return an estimation of the size. It doesn’t need to be correct, but it’s better too big than too small. The createOriginalMoveIterator method is called if the selectionOrder is ORIGINAL or if it is cached. The createRandomMoveIterator method is called for selectionOrder RANDOM combined with cacheType JUST_IN_TIME.

Don’t create a collection (array, list, set or map) of Moves when creating the Iterator<Move>: the whole purpose of MoveIteratorFactory over MoveListFactory is to create a Move just in time in a custom Iterator.next().

For example:

public class PossibleAssignmentsOnlyMoveIteratorFactory implements MoveIteratorFactory<MyPlanningSolution, MyChangeMove> {
    @Override
    public long getSize(ScoreDirector<MyPlanningSolution> scoreDirector) {
        // In this case, we return the exact size, but an estimate can be used
        // if it too expensive to calculate or unknown
        long totalSize = 0L;
        var solution = scoreDirector.getWorkingSolution();
        for (MyEntity entity : solution.getEntities()) {
            for (MyPlanningValue value : solution.getValues()) {
                if (entity.canBeAssigned(value)) {
                    totalSize++;
                }
            }
        }
        return totalSize;
    }

    @Override
    public Iterator<MyChangeMove> createOriginalMoveIterator(ScoreDirector<MyPlanningSolution> scoreDirector) {
        // Only needed if selectionOrder is ORIGINAL or if it is cached
        var solution = scoreDirector.getWorkingSolution();
        var entities = solution.getEntities();
        var values = solution.getValues();
        // Assumes each entity has at least one assignable value
        var firstEntityIndex = 0;
        var firstValueIndex = 0;
        while (!entities.get(firstEntityIndex).canBeAssigned(values.get(firstValueIndex))) {
            firstValueIndex++;
        }


        return new Iterator<>() {
            int nextEntityIndex = firstEntityIndex;
            int nextValueIndex = firstValueIndex;

            @Override
            public boolean hasNext() {
                return nextEntityIndex < entities.size();
            }

            @Override
            public MyChangeMove next() {
                var selectedEntity = entities.get(nextEntityIndex);
                var selectedValue = values.get(nextValueIndex);
                nextValueIndex++;
                while (nextValueIndex < values.size() && !selectedEntity.canBeAssigned(values.get(nextValueIndex))) {
                    nextValueIndex++;
                }
                if (nextValueIndex >= values.size()) {
                    // value list exhausted, go to next entity
                    nextEntityIndex++;
                    if (nextEntityIndex < entities.size()) {
                        nextValueIndex = 0;
                        while (nextValueIndex < values.size() && !entities.get(nextEntityIndex).canBeAssigned(values.get(nextValueIndex))) {
                            // Assumes each entity has at least one assignable value
                            nextValueIndex++;
                        }
                    }
                }
                return new MyChangeMove(selectedEntity, selectedValue);
            }
        };
    }

    @Override
    public Iterator<MyChangeMove> createRandomMoveIterator(ScoreDirector<MyPlanningSolution> scoreDirector,
            Random workingRandom) {
        // Not needed if selectionOrder is ORIGINAL or if it is cached
        var solution = scoreDirector.getWorkingSolution();
        var entities = solution.getEntities();
        var values = solution.getValues();

        return new Iterator<>() {
            @Override
            public boolean hasNext() {
                return !entities.isEmpty();
            }

            @Override
            public MyChangeMove next() {
                var selectedEntity = entities.get(workingRandom.nextInt(entities.size()));
                var selectedValue = values.get(workingRandom.nextInt(values.size()));
                while (!selectedEntity.canBeAssigned(selectedValue)) {
                    // This assumes there at least one value that can be assigned to the selected entity
                    selectedValue = values.get(workingRandom.nextInt(values.size()));
                }
                return new MyChangeMove(selectedEntity, selectedValue);
            }
        };
    }
}

The same effect can also be achieved using filtered selection.

Simple configuration (which can be nested in a unionMoveSelector just like any other MoveSelector):

    <moveIteratorFactory>
      <moveIteratorFactoryClass>...</moveIteratorFactoryClass>
    </moveIteratorFactory>

Advanced configuration:

    <moveIteratorFactory>
      ... <!-- Normal moveSelector properties -->
      <moveIteratorFactoryClass>...</moveIteratorFactoryClass>
      <moveIteratorFactoryCustomProperties>
        ...<!-- Custom properties -->
      </moveIteratorFactoryCustomProperties>
    </moveIteratorFactory>

To configure values of a MoveIteratorFactory dynamically in the solver configuration (so the Benchmarker can tweak those parameters), add the moveIteratorFactoryCustomProperties element and use custom properties.

A custom MoveIteratorFactory implementation must ensure that it does not move pinned entities.