Adjusting constraints at runtime

Deciding the correct weight and level for each constraint is not easy. It often involves negotiating with different stakeholders and their priorities. Furthermore, quantifying the impact of soft constraints is often a new experience for business managers, so they’ll need a number of iterations to get it right.

Don’t get stuck between a rock and a hard place. Provide a UI to adjust the constraint weights and visualize the resulting solution, so the business managers can tweak the constraint weights themselves:

parameterizeTheScoreWeights

1. Defining and overriding constraint weights

Let’s define three constraints:

  • Constraint with a name of Vehicle capacity and a weight of `1hard'.

  • Constraint with a name of Service finished after max end time, also with a weight of 1hard.

  • Constraint with a name of Minimize travel time and a weight of 1soft.

Using the Constraint Streams API, this is done as follows:

public class VehicleRoutingConstraintProvider implements ConstraintProvider {

    ...

    @Override
    public Constraint[] defineConstraints(ConstraintFactory factory) {
        return new Constraint[] {
                vehicleCapacity(factory),
                serviceFinishedAfterMaxEndTime(factory),
                minimizeTravelTime(factory)
        };
    }

    Constraint vehicleCapacity(ConstraintFactory factory) {
        return factory.forEach(Vehicle.class)
                ...
                .penalize(HardSoftScore.ONE_HARD, ...)
                .asConstraint("Vehicle capacity");
    }

    Constraint serviceFinishedAfterMaxEndTime(ConstraintFactory factory) {
        return factory.forEach(Visit.class)
                ...
                .penalize(HardSoftScore.ONE_HARD, ...)
                .asConstraint("Service finished after max end time");
    }

    Constraint minimizeTravelTime(ConstraintFactory factory) {
        return factory.forEach(Vehicle.class)
                ...
                .penalize(HardSoftScore.ONE_SOFT, ...)
                .asConstraint("Minimize travel time");
    }
}

Without anything else, the constraint weights are fixed to the values we’ve given them in our ConstraintProvider. To be able to override these weights at runtime, we need to introduce the ConstraintWeightOverrides class to our planning solution class:

@PlanningSolution
public class VehicleRoutePlan {

    ...

    ConstraintWeightOverrides<HardSoftScore> constraintWeightOverrides;

    void setConstraintWeightOverrides(ConstraintWeightOverrides<HardSoftScore> constraintWeightOverrides) {
        this.constraintWeightOverrides = constraintWeightOverrides;
    }

    ConstraintWeightOverrides<HardSoftScore> getConstraintWeightOverrides() {
        return constraintWeightOverrides;
    }

    ...
}

We’ve just introduced a new field of type ConstraintWeightOverrides, and we provided a getter and a setter for it. The field will be automatically exposed as a problem fact, there is no need to add a @ProblemFactProperty annotation. But we need to fill it with the desired constraint weights:

...

var constraintWeightOverrides = ConstraintWeightOverrides.of(
    Map.of(
        "Vehicle capacity", HardSoftScore.ofHard(2),
        "Service finished after max end time", HardSoftScore.ZERO
    )
);

var solution = new VehicleRoutePlan();
solution.setConstraintWeightOverrides(constraintWeightOverrides);

...

The Vehicle capacity constraint in this planning solution has a weight of 2hard, as opposed to its original 1hard. The Service finished after max end time constraint has a weight of 0hard, and therefore will be disabled entirely.

In this way, you can solve the same problem by applying different constraint weights to each instance. Once solved, you can compare the results and decide which set of weights is the most suitable for your use case.

1.1. Sending overrides over the wire

Overrides are part of the planning solution, and as such they are automatically serialized into JSON using Jackson, assuming either of the following conditions are met:

Overrides doesn’t natively deserialize from JSON back to Java objects. This is because we have no way of knowing which Score implementation you may be using. However, deserialization is easy to implement yourself by extending AbstractConstraintWeightOverridesDeserializer and registering it with Jackson’s ObjectMapper.

2. Passing parameters to constraints

In some cases, constraints need to be parameterized as different data sets may have different requirements for the same constraint. For example, a constraint may have to switch the minimum required pause length between two shifts, based on the laws of the country that the data set is dealing with.

To achieve this, you could have many variants of the same constraint in ConstraintProvider and disable some of them using overrides. To avoid the code duplication that this would have caused, it is arguably better to have a single constraint that can be parameterized. This section shows how to achieve this using the Constraint Streams API.

First, create a new class to hold the parameters for the constraint. For this document, we call it ConstraintParameters, but you’re free to choose any name you like:

public record ConstraintParameters(int minimumPauseInMinutes) {
}

Then, add a field of type ConstraintParameters to your planning solution and annotate it with @PlanningFactProperty:

@PlanningSolution
public record MyPlanningSolution {

    ...

    @PlanningFactProperty
    ConstraintParameters constraintParameters;

    ...

}

This will expose the ConstraintParameters as a problem fact, making it available to the constraints. Finally, use the join building block to adjust the constraint implementation to use the parameters:

public class MyConstraintProvider implements ConstraintProvider {

    ...

    Constraint minimumPauseBetweenShifts(ConstraintFactory factory) {
        return factory.forEach(Shift.class)
                .join(ConstraintParameters.class)
                .penalize(HardSoftScore.ONE_HARD, (shift, parameters) -> {
                    var pauseInMinutes = shift.getPauseInMinutes();
                    return Math.max(0, pauseInMinutes - constraintParameters.minimumPauseInMinutes());
                })
                .asConstraint("Minimum pause between shifts");
    }

    ...

}

3. Legacy constraint configuration using @ConstraintConfiguration

This feature is deprecated and will be removed in a future release of Timefold Solver. Please use constraint weight overrides instead.

First, create a new class to hold the constraint weights and other constraint parameters. Annotate it with @ConstraintConfiguration:

@ConstraintConfiguration
public class ConferenceConstraintConfiguration {
    ...
}

There will be exactly one instance of this class per planning solution. The planning solution and the constraint configuration have a one-to-one relationship, but they serve a different purpose, so they aren’t merged into a single class. A @ConstraintConfiguration class can extend a parent @ConstraintConfiguration class, which can be useful in international use cases with many regional constraints.

Add the constraint configuration on the planning solution and annotate that field or property with @ConstraintConfigurationProvider:

@PlanningSolution
public class ConferenceSchedule {

    @ConstraintConfigurationProvider
    private ConferenceConstraintConfiguration constraintConfiguration;

    ...
}

The @ConstraintConfigurationProvider annotation automatically exposes the constraint configuration as a problem fact, there is no need to add a @ProblemFactProperty annotation.

The constraint configuration class holds the constraint weights, but it can also hold constraint parameters. For example, in conference scheduling, the minimum pause constraint has a constraint weight (like any other constraint), but it also has a constraint parameter that defines the length of the minimum pause between two talks of the same speaker. That pause length depends on the conference (= the planning problem): in some big conferences 20 minutes isn’t enough to go from one room to the other. That pause length is a field in the constraint configuration without a @ConstraintWeight annotation.

3.1. Add a constraint weight for each constraint

In the constraint configuration class, add a @ConstraintWeight field or property for each constraint:

@ConstraintConfiguration
public class ConferenceConstraintConfiguration {

    @ConstraintWeight("Speaker conflict")
    private HardMediumSoftScore speakerConflict = HardMediumSoftScore.ofHard(10);

    @ConstraintWeight("Theme track conflict")
    private HardMediumSoftScore themeTrackConflict = HardMediumSoftScore.ofSoft(10);
    @ConstraintWeight("Content conflict")
    private HardMediumSoftScore contentConflict = HardMediumSoftScore.ofSoft(100);

    ...
}

The type of the constraint weights must be the same score class as the planning solution’s score member. For example, in conference scheduling, ConferenceSchedule.getScore() and ConferenceConstraintConfiguration.getSpeakerConflict() both return a HardMediumSoftScore.

A constraint weight can’t be null. Give each constraint weight a default value, but expose them in a UI so the business users can tweak them. The example above uses the ofHard(), ofMedium() and ofSoft() methods to do that. Notice how it defaults the "Content conflict" constraint as ten times more important than the "Theme track conflict" constraint. Normally, a constraint weight only uses one score level, but it’s possible to use multiple score levels (at a small performance cost).

Each constraint has a constraint name, and optionally a constraint package; together they form the constraint id. These connect the constraint weight with the constraint implementation. For each constraint weight, there must be a constraint implementation with the same constraint id.

Constraint packages are optional and have been deprecated. We recommend that you don’t use them, and instead keep constraint names unique. If constraint package is not provided, the solver will transparently provide a default value.

  • The @ConstraintConfiguration annotation has a constraintPackage property that defaults to the package of the constraint configuration class. Cases with Constraint Streams API normally don’t need to specify it.

  • The @ConstraintWeight annotation has a value which is the constraint name (for example "Speaker conflict"). It inherits the constraint package from the @ConstraintConfiguration, but it can override that, for example @ConstraintWeight(constraintPackage = "…​region.france", …​) to use a different constraint package than some other weights.

So every constraint weight ends up with a constraint package and a constraint name. Each constraint weight links with a constraint implementation, for example, in Constraint Streams API:

public class ConferenceSchedulingConstraintProvider implements ConstraintProvider {

    @Override
    public Constraint[] defineConstraints(ConstraintFactory factory) {
        return new Constraint[] {
                speakerConflict(factory),
                themeTrackConflict(factory),
                contentConflict(factory),
                ...
        };
    }

    protected Constraint speakerConflict(ConstraintFactory factory) {
        return factory.forEachUniquePair(...)
                ...
                .penalizeConfigurable("Speaker conflict", ...);
    }

    protected Constraint themeTrackConflict(ConstraintFactory factory) {
        return factory.forEachUniquePair(...)
                ...
                .penalizeConfigurable("Theme track conflict", ...);
    }

    protected Constraint contentConflict(ConstraintFactory factory) {
        return factory.forEachUniquePair(...)
                ...
                .penalizeConfigurable("Content conflict", ...);
    }

    ...

}

Each of the constraint weights defines the score level and score weight of their constraint. The constraint implementation calls rewardConfigurable() or penalizeConfigurable() and the constraint weight is automatically applied.

If the constraint implementation provides a match weight, that match weight is multiplied with the constraint weight. For example, the "Content conflict" constraint weight defaults to 100soft and the constraint implementation penalizes each match based on the number of shared content tags and the overlapping duration of the two talks:

    @ConstraintWeight("Content conflict")
    private HardMediumSoftScore contentConflict = HardMediumSoftScore.ofSoft(100);
Constraint contentConflict(ConstraintFactory factory) {
    return factory.forEachUniquePair(Talk.class,
        overlapping(t -> t.getTimeslot().getStartDateTime(),
            t -> t.getTimeslot().getEndDateTime()),
        filtering((talk1, talk2) -> talk1.overlappingContentCount(talk2) > 0))
        .penalizeConfigurable("Content conflict",
                (talk1, talk2) -> talk1.overlappingContentCount(talk2)
                        * talk1.overlappingDurationInMinutes(talk2));
}

So when 2 overlapping talks share only 1 content tag and overlap by 60 minutes, the score is impacted by -6000soft. But when 2 overlapping talks share 3 content tags, the match weight is 180, so the score is impacted by -18000soft.