Examples for an implementation of MoveIteratorFactory

[EverettZ]

I've got some sort of knowledge gap here. I cant seem to figure out how to properly implement MoveIteratorFactory.

Are there any example implementations laying around? The documentation for it is a little sparse.

[Christopher-Chianelli]

Currently, there are no example/quickstart that utilize it, but here an 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
        throw new UnsupportedOperationException();
    }

    @Override
    public Iterator<MyChangeMove> createRandomMoveIterator(ScoreDirector<MyPlanningSolution> scoreDirector,
            Random workingRandom) {
        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);
            }
        };
    }
}

[Christopher-Chianelli]

Ideally, the iterator should be written so it only return moves that will likely improve the solution/doesn't violate any hard constraints (provided it not too expensive to calculate), since the iterator can exploit properties of the working solution that it knows about (which Timefold cannot do in the general case with its default move selectors which need to work across all different kinds of planning problems).

[EverettZ]

Thanks for the response. I ended up somewhat figuring it out. But you've made me rethink a couple things...

Couple questions:

1. Getting entities and values prior to returning the iterator is correct?
2. Is the canBeAssigned check totally necessary if the move itself requires an implementation of isMoveDoable?
3. If there are cases where I cannot assume there is at least one value that can be assigned (overconstrained), then how would you recommend filtering moves in this example? I cant think of how to accomplish that without creating infinite loops.

[Christopher-Chianelli]

1. You can get entities and values before creating/returning the iterator.
2. You can do the filtering in isMoveDoable (or not do any filtering at all).
3. You can return a non-doable move in the iterator (either bail out after a certain number of times, or don't do any filtering at the iterator level and rely on the filtering on the Move (via isMoveDoable) level).

[EverettZ]

Okay great, thanks. That lines up with my train of thought.

Last follow up, #3, how would you "bail out" within the next() call?

[Christopher-Chianelli]

Return a new NoChangeMove<>(), like this:

public class PossibleAssignmentsOnlyMoveIteratorFactory implements MoveIteratorFactory<MyPlanningSolution, Move<MyPlanningSolution>> {
    // ...
     @Override
    public Iterator<Move<MyPlanningSolution>> createRandomMoveIterator(ScoreDirector<MyPlanningSolution> scoreDirector,
            Random workingRandom) {
        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()));
                if (!selectedEntity.canBeAssigned(selectedValue)) {
                    // bail out
                    return new NoChangeMove<>();
                }
                return new MyChangeMove(selectedEntity, selectedValue);
            }
        };
    }
}