BiConstraintCollector doesn't

[thimmwork]

Describe the bug
I'm implementing a custom BiConstraintCollector for use in groupBy() constraint streams.
For some reason, the elements are not collected, the provided ResultContainer remains empty, and the constraint doesn't penalize.
It might very well be that I'm using the API wrong (e.g. the two consecutive calls of groupBy come to mind). I'll gladly take advice in any direction.

Expected behavior
Invocation of the Runnables for each tuple. Passing of the test.

Actual behavior
The Runnables are not invoked. The test fails with

java.lang.AssertionError: Broken expectation.
        Constraint: ai.timefold.solver.examples.cloudbalancing.domain/differenceInRequiredCpu
  Expected penalty: 1 (class java.lang.Integer)
    Actual penalty: 0 (class java.lang.Integer)

  Explanation of score (0hard/0soft):
    Constraint matches:
        0: constraint (differenceInRequiredCpu) has 1 matches:
            0: justified with ([{}])
    Indictments:
        0: indicted with ({}) has 1 matches:
            0: constraint (differenceInRequiredCpu)

To Reproduce

My minimal example is based on the CloudBalancing example, and introduces the following additional constraint (which seems odd in this particular example, but for demonstration purposes I hope it'll do):
For each computer, I want to penalize the scheduling of processes that have different cpu requirements. And I want to do this in a per-computer way, so the cost doesn't explode when scheduling lots of small tasks.
So I implemented a MinMaxCollector, with the intention to determine the minimum and maximum cpu requirements of scheduled processes per computer.

I forked the timefold-solver repo and added my BiConstraintCollector, the additional constraint and a unit test here:
https://github.com/thimmwork/timefold-solver/blob/4862eef96575fc061eb5b5cb0727b791790e184a/examples/src/test/java/ai/timefold/solver/examples/cloudbalancing/score/CloudBalancingConstraintProviderTest.java#L84C21-L84C21

This is the constraint I added to CloudBalancingConstraintProvider.
I'm using the computer.id as key and want to collect the min and max requiredCpuPower of all the processes assigned to each computer.

   Constraint differenceInRequiredCpu(ConstraintFactory constraintFactory) {
        return constraintFactory.forEach(CloudProcess.class)
                .filter(cloudProcess -> cloudProcess.getComputer() != null)
                .groupBy(cloudProcess -> cloudProcess.getComputer().getId(), cloudProcess -> cloudProcess.getRequiredCpuPower())
                .groupBy(MinMaxCollector.collector())
                .penalize(HardSoftScore.ONE_HARD,
                        cpuPowerByComputer -> penalizeByCpuDifference(cpuPowerByComputer.values()))
                .asConstraint("differenceInRequiredCpu");
    }

    private Integer penalizeByCpuDifference(Collection<Pair<Integer, Integer>> minAndMaxCpuByComputer) {
        return minAndMaxCpuByComputer.stream()
                .mapToInt(minMax -> minMax.getRight() - minMax.getLeft())
                // use the square to penalize bigger differences way more than smaller differences
                .map(difference -> difference * difference)
                .sum();
    }

This is my Collector (for easier code analysis I'm using anonymous classes here)

public class MinMaxCollector<KEY, COMP extends Comparable<COMP>> {
    private final Map<KEY, Pair<COMP, COMP>> minMaxPerKey = new HashMap<>();

    public void collect(KEY key, COMP other) {
        var minMax = minMaxPerKey.get(key);
        var replace = false;
        if (minMax == null) {
            minMax = ImmutablePair.of(other, other);
            replace = true;
        } else if (minMax.getLeft().compareTo(other) > 0) {
            minMax = ImmutablePair.of(other, minMax.getRight());
            replace = true;
        }
        if (minMax.getRight().compareTo(other) < 0) {
            minMax = ImmutablePair.of(minMax.getLeft(), other);
            replace = true;
        }
        if (replace) {
            minMaxPerKey.put(key, minMax);
        }
    }

    public Map<KEY, Pair<COMP, COMP>> getMinMaxPerKey() {
        return minMaxPerKey;
    }

    public static <KEY, COMP extends Comparable<COMP>>
            BiConstraintCollector<KEY, COMP, MinMaxCollector<KEY, COMP>, Map<KEY, Pair<COMP, COMP>>> collector() {
        return new BiConstraintCollector<>() {
            @Override
            public Supplier<MinMaxCollector<KEY, COMP>> supplier() {
                return MinMaxCollector::new;
            }

            @Override
            public TriFunction<MinMaxCollector<KEY, COMP>, KEY, COMP, Runnable> accumulator() {
                return new TriFunction<MinMaxCollector<KEY, COMP>, KEY, COMP, Runnable>() {
                    @Override
                    public Runnable apply(MinMaxCollector<KEY, COMP> minMaxCollector, KEY key, COMP comp) {
                        return new Runnable() {
                            @Override
                            public void run() {
                                minMaxCollector.collect(key, comp);
                            }
                        };
                    }
                };
            }

            @Override
            public Function<MinMaxCollector<KEY, COMP>, Map<KEY, Pair<COMP, COMP>>> finisher() {
                return MinMaxCollector::getMinMaxPerKey;
            }
        };
    }
}

and a unit test that I added to CloudBalancingConstraintProviderTest:

    @ConstraintProviderTest
    void useThisTestToReproduce(ConstraintVerifier<CloudBalancingConstraintProvider, CloudBalance> constraintVerifier) {
        CloudComputer computer1 = new CloudComputer(1, 1, 1, 1, 2);
        CloudProcess process1 = new CloudProcess(1, 1, 1, 1);
        CloudProcess process2 = new CloudProcess(2, 3, 1, 1);
        process1.setComputer(computer1);
        process2.setComputer(computer1);

        constraintVerifier.verifyThat(CloudBalancingConstraintProvider::differenceInRequiredCpu)
                .given(computer1, process1, process2)
                .penalizesBy(1);
    }

My expectation would be that the above unit test would trigger the same invocations as this test, which tests the collector directly:

    @Test
    public void biconstraintcollector_smoke_test() {
        //given
        Integer computerId = 1;
        BiConstraintCollector<Integer, Integer, MinMaxCollector<Integer, Integer>, Map<Integer, Pair<Integer, Integer>>> biConstraintCollector = MinMaxCollector.collector();

        //when
        MinMaxCollector<Integer, Integer> minMaxCollector = biConstraintCollector.supplier().get();
        TriFunction<MinMaxCollector<Integer, Integer>, Integer, Integer, Runnable> accumulator = biConstraintCollector.accumulator();

        // A: min=1, max=10
        accumulator.apply(minMaxCollector, computerId, 1).run();
        accumulator.apply(minMaxCollector, computerId, 3).run();

        //then
        var finisher = biConstraintCollector.finisher().apply(minMaxCollector);
        assertEquals(1, finisher.get(computerId).getLeft());
        assertEquals(3, finisher.get(computerId).getRight());
    }

This test works, so the problem is either outside of the BiConstraintCollector or in my understanding.

Environment

Timefold Solver Version or Git ref:
tested on solver 1.20, 1.4.0, 1.5.0 and git commit 490490a (current main)

Output of java -version:
openjdk 17.0.9 2023-10-17
OpenJDK Runtime Environment Temurin-17.0.9+9 (build 17.0.9+9)
OpenJDK 64-Bit Server VM Temurin-17.0.9+9 (build 17.0.9+9, mixed mode)

Output of uname -a or ver:
Darwin WYJTH5W7YK 22.6.0 Darwin Kernel Version 22.6.0: Fri Sep 15 13:41:28 PDT 2023; root:xnu-8796.141.3.700.8~1/RELEASE_ARM64_T6000 arm64

Additional information

Provide any and all other information which might be relevant to the issue.

[triceo]

Hey there!

The problem appears to be in your accumulator. You need something like this:

 @Override
 public TriFunction<MinMaxCollector<KEY, COMP>, KEY, COMP, Runnable> accumulator() {
   // Insert code that does the accumulation. This is your `collect(...)` function.
   
   // Now return a new Runnable which can *undo* that accumulation,
   // removing the match from `MinMaxCollector`.
 }

In your accumulator, you're only returning the undo Runnable, and that means that nothing gets accumulated. There is no code to actually accumulate anything.

I'll convert this issue to a discussion, as my current understanding indicates this is not a solver problem. If there's still something to explain, we can continue there.

[triceo]

Side note: if you need a minMax collector, you can compose(...) the min and max collectors, although yours will be more efficient (when it works), because it only keeps one data structure for both min and max.

[thimmwork]

Thank you very much, @triceo!
I misunderstood how the accumulator is supposed to work and fixed it.
That solved my problem.

For anyone encountering a similar task, below you'll find the corrected and simplified Collector.
Some implementation notes:
I used apache common's ListValuedHashMap (which is already is on the classpath), because it needs to retain the full list of tuples for lossless undos. That also took away much of the code.
It is not thread-safe. The BiConstraintCollector javadoc doesn't mention thread-safety, so I assume it is not a problem.
The map returned by the finisher is not immutable, though this is recommended in the javadoc.

    /**
     * @return a Timefold BiConstraintCollector that uses the first fact as a key and collects min and max values of the second fact.
     * The second fact must implement Comparable
     * @param <KEY> key to group the values
     * @param <COMP> comparable of which to determine the min and the max
     */
    public static <KEY, COMP extends Comparable<COMP>> BiConstraintCollector<KEY, COMP, MultiValuedMap<KEY, COMP>, Map<KEY, Pair<COMP, COMP>>> collector() {
        return new BiConstraintCollector<>() {
            @Override
            public Supplier<MultiValuedMap<KEY, COMP>> supplier() {
                return MultiMapUtils::newListValuedHashMap;
            }

            @Override
            public TriFunction<MultiValuedMap<KEY, COMP>, KEY, COMP, Runnable> accumulator() {
                return (listMultimap, key1, other) -> {
                    listMultimap.put(key1, other);
                    return () -> listMultimap.removeMapping(key1, other);
                };
            }

            @Override
            public Function<MultiValuedMap<KEY, COMP>, Map<KEY, Pair<COMP, COMP>>> finisher() {
                return listMultimap -> {
                    Map<KEY, Pair<COMP, COMP>> map = new HashMap<>();
                    for (var key : listMultimap.keySet()) {
                        var values = listMultimap.get(key);
                        var min = Collections.min(values);
                        var max = Collections.max(values);
                        map.put(key, ImmutablePair.of(min, max));
                    }
                    return map;
                };
            }
        };
    }

[triceo]

Glad you got it to work! Some comments:

• Thread safety is not a problem. CS always runs single-threaded; when you enable multi-threaded solving, it actually runs multiple independent CS in parallel.
• Your finisher is not incremental - building up the map this way will kill your performance; not only do you iterate over the entire container map, you then iterate twice over every value in that map. Supporting incrementality is the only reason why collectors are designed in this non-obvious way. I recommend that you figure out a way to build this map on the fly in the accumulator. In the finisher, pretty much just do return Collections.unmodifiableMap(...); or don't do anything at all and just return the map.

[thimmwork]

Thanks again.
This version uses an incremental approach and works fine for me:
https://gist.github.com/thimmwork/b389dedfe3a0a36c8b5be52aae191e47

I also came across a slightly more generic usecase where I wanted to collect sets of distincts elements.
https://gist.github.com/thimmwork/64c525a15ceb601cae51eeb20400ff76
If you see value in these ConstraintCollectors, I'm happy to provide a PR.

[triceo]

The ConstraintCollector class has been getting somewhat crowded - I'd prefer to only add things in there after we see significant demand. (Such as the recently added consecutive collector, which solves a frequent problem.)

That said, I still find it interesting to gather these little things somewhere - it'd be a shame if they went away. Maybe we start a new repo where these are stored as examples people can just copy over? Each collector is fully documented, each has full test coverage, and people can use the repo as a "grocery store" - browse the shelves, pick what you like, take it home.

WDYT @thimmwork ? What would be your idea?

[thimmwork]

While writing my answer, I just realized that my use case is covered by the toSet() collector. And I saw that the collector implementation were recently moved so that ConstraintCollectors merely acts as a facade. I like that because it strikes a balance between easy discoverability for users to find available collectors and separation of all the implementations in the code.

Concluding from that, the only use case I was missing was collecting both the min and max at the same time, which is a special case of the toSortedSet() (because to work incremental, you have to retain the set).
I managed to replace the MinMaxCollector with toSortedSet() which since Java 21's SequencedCollection even offers a getFirst() and getLast() which give me exactly the min and max I need:

                .groupBy((key, value)  -> key, toSortedSet((BiFunction<.., Long, Long>) (key, value) -> value))
                .penalizeLong(ONE_SOFT, (key, valueSet) -> times.getLast() - times.getLast()))

And I expect other use cases to look similar: They probably are either mathematical aggregations similar to min/max/count/avg or operate on collections of collected items, for which there are toCollection, toSet, toSortedSet, toMap and toSortedMap where the last two even offer the ValueSet-variants.

So maybe there is not a real need for additional collectors - at least not to cover my use cases.

That said, to satisfy my sunk-cost fellacy, I'll post my original answer, maybe it provides value when the question comes up again:

Putting it into a separate repo has 3 downsides:

1. User Experience. As a developer, I want to have low barriers when implementing and tuning Constraints. They are the core of each implementation and probably the most complex part of Timefold's API most users deal with (under the assumption most manage to skip custom move implementation and custom entity/value selection). So I assume most will use auto-completion to find available ConstraintCollector implementations, and code in a separate repo won't be listed there. A facade like ConstraintCollectors is very convenient here, and I'm glad to see the ConsecutiveCollectors were added there.
2. Copy/Pasta. Even if the code is well-tested: Once it is copied to an individual project, it is disconnected from the source. This means it won't be updated with any improvements (previously unspotted bugs, usability improvements, feature enhancements) and increase complexity on the user side. Do we expect users to take responsibility for migrating these implementations to future Timefold versions? This could only be mitigated by having a release artifact, that would probably have to be bound in some way to Timefold's release cycle, to not have to maintain a compatibility matrix.
3. It doesn't solve the underlying problem that for each additional collector that isn't part of solver-core, you have to copy or reimplement functionality because classes are package-private or sealed. The separate repo would have to provide its own implementations for ObjectCalculator etc. or - even worse - each copyable collector recipe would have to bring its own. This could be mitigated by opening sealed classes in solver-core and increasing class accessibility, which of course comes with other downsides.

It's complicated. I for one learned from this discussion (and by playing with the code), that I previously over-estimated my understanding of the Constraint Streams API.
And looking at Timefold's documentation (which I would say has a blind spot for constraint streams that probably stems from the era of drools-only), it's probably worth to challenge the perceived need for additional collectors by providing a better overview over what's already there and how it can be used. Because what's there is awesome, and you can proudly present it.

Happy new year :)

[triceo]

Thanks for the exhaustive answer! One thing caught my eye there among others:

And looking at Timefold's documentation (which I would say has a blind spot for constraint streams that probably stems from the era of drools-only), it's probably worth to challenge the perceived need for additional collectors by providing a better overview over what's already there and how it can be used. Because what's there is awesome, and you can proudly present it.

Personally, I never thought of CS as under-documented. What do you think is missing?
(This is actually a prime spot for a PR!)

Happy new year to you as well!