////
Licensed to the Apache Software Foundation (ASF) under one
or more contributor license agreements.  See the NOTICE file
distributed with this work for additional information
regarding copyright ownership.  The ASF licenses this file
to you under the Apache License, Version 2.0 (the
"License"); you may not use this file except in compliance
with the License.  You may obtain a copy of the License at

  http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing,
software distributed under the License is distributed on an
"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
KIND, either express or implied.  See the License for the
specific language governing permissions and limitations
under the License.
////

[[shadowVariable]]
= Shadow variable
:doctype: book
:sectnums:
:icons: font


[[shadowVariableIntroduction]]
== Introduction

A shadow variable is a planning variable whose correct value can be deduced from the state of the xref:planner-configuration/planner-configuration.adoc#planningVariable[genuine planning variables].
Even though such a variable violates the principle of normalization by definition, in some use cases it can be very practical to use a shadow variable, especially to express the constraints more naturally.
For example in vehicle routing with time windows: the arrival time at a customer for a vehicle can be calculated based on the previously visited customers of that vehicle (and the known travel times between two locations).

image::shadow-variable/planningVariableListener.png[align="center"]

When the customers for a vehicle change, the arrival time for each customer is automatically adjusted.
For more information, see the xref:use-cases-and-examples/vehicle-routing/vehicle-routing.adoc#vehicleRoutingDomainModel[vehicle routing domain model].

From a score calculation perspective, a shadow variable is like any other planning variable.
From an optimization perspective, OptaPlanner effectively only optimizes the genuine variables (and mostly ignores the shadow variables): it just assures that when a genuine variable changes, any dependent shadow variables are changed accordingly.

[IMPORTANT]
====
**Any class that has at least one shadow variable, is a planning entity class (even if it has no genuine planning variables).
That class must be defined in the solver configuration and have a `@PlanningEntity` annotation.**

A genuine planning entity class has at least one genuine planning variable, but can have shadow variables too.
A shadow planning entity class has no genuine planning variables and at least one shadow planning variable.
====

There are several built-in shadow variables:


[[bidirectionalVariable]]
== Bi-directional variable (inverse relation shadow variable)

Two variables are bi-directional if their instances always point to each other (unless one side points to `null` and the other side does not exist).
So if A references B, then B references A.

image::shadow-variable/bidirectionalVariable.png[align="center"]

For a non-chained planning variable, the bi-directional relationship must be a many-to-one relationship.
To map a bi-directional relationship between two planning variables, annotate the source side (which is the genuine side) as a normal planning variable:

[source,java,options="nowrap"]
----
@PlanningEntity
public class CloudProcess {

    @PlanningVariable(...)
    public CloudComputer getComputer() {
        return computer;
    }
    public void setComputer(CloudComputer computer) {...}

}
----

And then annotate the other side (which is the shadow side) with a `@InverseRelationShadowVariable` annotation on a `Collection` (usually a `Set` or ``List``) property:

[source,java,options="nowrap"]
----
@PlanningEntity
public class CloudComputer {

    @InverseRelationShadowVariable(sourceVariableName = "computer")
    public List<CloudProcess> getProcessList() {
        return processList;
    }

}
----

<<shadowVariableIntroduction,Register this class as a planning entity>>,
otherwise OptaPlanner won't detect it and the shadow variable won't update.
The `sourceVariableName` property is the name of the genuine planning variable on the return type of the getter
(so the name of the genuine planning variable on the _other_ side).

[NOTE]
====
The shadow property, which is ``Collection`` (usually `List`, `Set` or `SortedSet`), can never be ``null``.
If no genuine variable references that shadow entity, then it is an empty collection.
Furthermore it must be a mutable `Collection` because once OptaPlanner starts initializing or changing genuine planning variables,
it will add and remove elements to the ``Collection``s of those shadow variables accordingly.
====

For a chained planning variable, the bi-directional relationship is always a one-to-one relationship.
In that case, the genuine side looks like this:

[source,java,options="nowrap"]
----
@PlanningEntity
public class Customer ... {

    @PlanningVariable(graphType = PlanningVariableGraphType.CHAINED, ...)
    public Standstill getPreviousStandstill() {
        return previousStandstill;
    }
    public void setPreviousStandstill(Standstill previousStandstill) {...}

}
----

And the shadow side looks like this:

[source,java,options="nowrap"]
----
@PlanningEntity
public class Standstill {

    @InverseRelationShadowVariable(sourceVariableName = "previousStandstill")
    public Customer getNextCustomer() {
         return nextCustomer;
    }
    public void setNextCustomer(Customer nextCustomer) {...}

}
----

<<shadowVariableIntroduction,Register this class as a planning entity>>,
otherwise OptaPlanner won't detect it and the shadow variable won't update.

[WARNING]
====
The input planning problem of a `Solver` must not violate bi-directional relationships.
If A points to B, then B must point to A.
OptaPlanner will not violate that principle during planning, but the input must not violate it either.
====


[[anchorShadowVariable]]
== Anchor shadow variable

An anchor shadow variable is the anchor of xref:planner-configuration/planner-configuration.adoc#chainedPlanningVariable[a chained variable].

Annotate the anchor property as a `@AnchorShadowVariable` annotation:

[source,java,options="nowrap"]
----
@PlanningEntity
public class Customer {

    @AnchorShadowVariable(sourceVariableName = "previousStandstill")
    public Vehicle getVehicle() {...}
    public void setVehicle(Vehicle vehicle) {...}

}
----

<<shadowVariableIntroduction,This class should already be registered as a planning entity.>>
The `sourceVariableName` property is the name of the chained variable on the same entity class.


[[listVariableShadowVariables]]
== List variable shadow variables

When the planning entity uses a xref:planner-configuration/planner-configuration.adoc#planningListVariable[list variable], its elements can use a number of built-in shadow variables.

=== Inverse relation shadow variable

Use the same `@InverseRelationShadowVariable` annotation as with basic or chained planning variable to establish bi-directional relationship between the entity and the elements assigned to its list variable.
The type of the inverse shadow variable is the planning entity itself because there is a one-to-many relationship between the entity and the element classes.

The planning entity side has a genuine list variable:

[source,java]
----
@PlanningEntity
public class Vehicle {

    @PlanningListVariable
    public List<Customer> getCustomers() {
        return customers;
    }

    public void setCustomers(List<Customer> customers) {...}
}
----

On the element side:

- Annotate the class with `@PlanningEntity` to make it a shadow planning entity.
- <<shadowVariableIntroduction,Register this class as a planning entity>>, otherwise OptaPlanner won't detect it and the shadow variable won't update.
- Create a property with the genuine planning entity type.
- Annotate it with `@InverseRelationShadowVariable` and set `sourceVariableName` to the name of the genuine planning list variable.

[source,java]
----
@PlanningEntity
public class Customer {

    @InverseRelationShadowVariable(sourceVariableName = "customers")
    public Vehicle getVehicle() {
        return vehicle;
    }

    public void setVehicle(Vehicle vehicle) {...}
}
----

=== Previous and next element shadow variable

Use `@PreviousElementShadowVariable` or `@NextElementShadowVariable` to get a reference to an element that is assigned to the same entity's list variable one index lower (previous element) or one index higher (next element).

[NOTE]
====
The previous and next element shadow variables may be `null` even in a fully initialized solution.
The first element's previous shadow variable is `null` and the last element's next shadow variable is `null`.
====

The planning entity side has a genuine list variable:

[source,java]
----
@PlanningEntity
public class Vehicle {

    @PlanningListVariable
    public List<Customer> getCustomers() {
        return customers;
    }

    public void setCustomers(List<Customer> customers) {...}
}
----

On the element side:

[source,java]
----
@PlanningEntity
public class Customer {

    @PreviousElementShadowVariable(sourceVariableName = "customers")
    public Customer getPreviousCustomer() {
        return previousCustomer;
    }

    public void setPreviousCustomer(Customer previousCustomer) {...}

    @NextElementShadowVariable(sourceVariableName = "customers")
    public Customer getNextCustomer() {
        return nextCustomer;
    }

    public void setNextCustomer(Customer nextCustomer) {...}
----

[[customVariableListener]]
== Custom `VariableListener`

To update a shadow variable, OptaPlanner uses a ``VariableListener``.
To define a custom shadow variable, write a custom ``VariableListener``:
implement the interface and annotate it on the shadow variable that needs to change.

[source,java,options="nowrap"]
----
    @PlanningVariable(...)
    public Standstill getPreviousStandstill() {
        return previousStandstill;
    }

    @ShadowVariable(
            variableListenerClass = VehicleUpdatingVariableListener.class,
            sourceVariableName = "previousStandstill")
    public Vehicle getVehicle() {
        return vehicle;
    }
----

<<shadowVariableIntroduction,Register this class as a planning entity>> if it isn't already.
Otherwise OptaPlanner won't detect it and the shadow variable won't update.

The `sourceVariableName` is the (genuine or shadow) variable that triggers changes to the annotated shadow variable.
If the source variable is declared on a different class than the annotated shadow variable's class, also specify the `sourceEntityClass` and make sure the shadow variable's class is <<shadowVariableIntroduction,registered as a planning entity>>.

Implement the `VariableListener` interface.
For example, the `VehicleUpdatingVariableListener` assures that every `Customer` in a chain has the same ``Vehicle``, namely the chain's anchor.

[source,java,options="nowrap"]
----
public class VehicleUpdatingVariableListener implements VariableListener<VehicleRoutingSolution, Customer> {

    public void afterEntityAdded(ScoreDirector<VehicleRoutingSolution> scoreDirector, Customer customer) {
        updateVehicle(scoreDirector, customer);
    }

    public void afterVariableChanged(ScoreDirector<VehicleRoutingSolution> scoreDirector, Customer customer) {
        updateVehicle(scoreDirector, customer);
    }

    ...

    protected void updateVehicle(ScoreDirector<VehicleRoutingSolution> scoreDirector, Customer sourceCustomer) {
        Standstill previousStandstill = sourceCustomer.getPreviousStandstill();
        Vehicle vehicle = previousStandstill == null ? null : previousStandstill.getVehicle();
        Customer shadowCustomer = sourceCustomer;
        while (shadowCustomer != null && shadowCustomer.getVehicle() != vehicle) {
            scoreDirector.beforeVariableChanged(shadowCustomer, "vehicle");
            shadowCustomer.setVehicle(vehicle);
            scoreDirector.afterVariableChanged(shadowCustomer, "vehicle");
            shadowCustomer = shadowCustomer.getNextCustomer();
        }
    }

}
----

[WARNING]
====
A `VariableListener` can only change shadow variables.
It must never change a genuine planning variable or a problem fact.
====

[WARNING]
====
Any change of a shadow variable must be told to the ``ScoreDirector`` with `before*()` and `after*()` methods.
====

=== Multiple source variables

If your custom variable listener needs multiple source variables to compute the shadow variable, annotate the shadow variable with multiple `@ShadowVariable` annotations, one per each source variable.

[source,java]
----
    @PlanningVariable(...)
    public ExecutionMode getExecutionMode() {
        return executionMode;
    }

    @PlanningVariable(...)
    public Integer getDelay() {
        return delay;
    }

    @ShadowVariable(
            variableListenerClass = PredecessorsDoneDateUpdatingVariableListener.class,
            sourceVariableName = "executionMode")
    @ShadowVariable(
            variableListenerClass = PredecessorsDoneDateUpdatingVariableListener.class,
            sourceVariableName = "delay")
    public Integer getPredecessorsDoneDate() {
        return predecessorsDoneDate;
    }
----

=== Piggyback shadow variable

If one `VariableListener` changes two or more shadow variables (because having two separate ``VariableListener``s would be inefficient), then annotate only the first shadow variable with `@ShadowVariable` and specify the `variableListenerClass` there.
Use `@PiggybackShadowVariable` on each shadow variable updated by that variable listener and reference the first shadow variable:

[source,java,options="nowrap"]
----
    @PlanningVariable(...)
    public Standstill getPreviousStandstill() {
        return previousStandstill;
    }

    @ShadowVariable(
            variableListenerClass = TransportTimeAndCapacityUpdatingVariableListener.class,
            sourceVariableName = "previousStandstill")
    public Integer getTransportTime() {
        return transportTime;
    }

    @PiggybackShadowVariable(shadowVariableName = "transportTime")
    public Integer getCapacity() {
        return capacity;
    }
----

=== Shadow variable cloning

A shadow variable's value (just like a genuine variable's value)
isn't xref:planner-configuration/planner-configuration.adoc#cloningASolution[planning cloned] by the default solution cloner,
unless it can easily prove that it must be planning cloned (for example the property type is a planning entity class).
Specifically shadow variables of type `List`, `Set`, `Collection` or `Map` usually need to be planning cloned
to avoid corrupting the best solution when the working solution changes.
To planning clone a shadow variable, add `@DeepPlanningClone` annotation:

[source,java,options="nowrap"]
----
    @DeepPlanningClone
    @ShadowVariable(...)
    private Map<LocalDateTime, Integer> usedManHoursPerDayMap;
----


[[variableListenerTriggeringOrder]]
== VariableListener triggering order

All shadow variables are triggered by a ``VariableListener``, regardless if it's a built-in or a custom shadow variable.
The genuine and shadow variables form a graph, that determines the order in which the ``afterEntityAdded()``, `afterVariableChanged()` and `afterEntityRemoved()` methods are called:

image::shadow-variable/shadowVariableOrder.png[align="center"]

[NOTE]
====
In the example above, D could have also been ordered after E (or F) because there is no direct or indirect dependency between D and E (or F).
====

OptaPlanner guarantees that:

* The first ``VariableListener``'s `after*()` methods trigger _after_ the last genuine variable has changed. Therefore the genuine variables (A and B in the example above) are guaranteed to be in a consistent state across all its instances (with values A1, A2 and B1 in the example above) because the entire `Move` has been applied.
* The second ``VariableListener``'s `after*()` methods trigger _after_ the last first shadow variable has changed. Therefore the first shadow variable (C in the example above) are guaranteed to be in a consistent state across all its instances (with values C1 and C2 in the example above). And of course the genuine variables too.
* And so forth.

OptaPlanner does not guarantee the order in which the `after*()` methods are called for the _same_``VariableListener`` with different parameters (such as A1 and A2 in the example above), although they are likely to be in the order in which they were affected.

By default, OptaPlanner does not guarantee that the events are unique.
For example, if a shadow variable on an entity is changed twice in the same move (for example by two different genuine variables), then that will cause the same event twice on the ``VariableListener``s that are listening to that original shadow variable.
To avoid dealing with that complexity, overwrite the method `requiresUniqueEntityEvents()` to receive unique events at the cost of a small performance penalty:

[source,java,options="nowrap"]
----
public class StartTimeUpdatingVariableListener implements VariableListener<TaskAssigningSolution, Task> {

    @Override
    public boolean requiresUniqueEntityEvents() {
        return true;
    }

    ...
}
----
