Shadow variable

1. Introduction

A shadow variable is a planning variable whose correct value can be deduced from the state of the 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).

planningVariableListener

When the customers for a vehicle change, the arrival time for each customer is automatically adjusted.

From a score calculation perspective, a shadow variable is like any other planning variable. From an optimization perspective, OptaPy 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.

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 be decorated with @planning_entity.

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:

2. 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 None and the other side does not exist). So if A references B, then B references A.

bidirectionalVariable

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:

from optapy import planning_entity, planning_variable

@planning_entity
class CloudProcess:
    @planning_variable(...)
    def get_computer(self):
        return self.computer

    def set_computer(self, computer):
        ...

And then annotate the other side (which is the shadow side) with a @inverse_relation_shadow_variable annotation on a list property:

from optapy import planning_entity, inverse_relation_shadow_variable

@planning_entity
class CloudComputer:
    # ...
    @inverse_relation_shadow_variable(source_variable_name = "computer")
    def get_process_list(self):
        return self.process_list
    ...

Register this class as a planning entity, otherwise OptaPy won’t detect it and the shadow variable won’t update. The source_variable_name parameter 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).

The shadow property, which is a list, can never be None. If no genuine variable references that shadow entity, then it is an empty list. Furthermore it must be a mutable list because once OptaPy starts initializing or changing genuine planning variables, it will add and remove elements to the lists 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:

from optapy import planning_entity, planning_variable
from optapy.types import PlanningVariableGraphType

@planning_entity
class Customer:
    @planning_variable(object, graph_type = PlanningVariableGraphType.CHAINED, ...)
    def get_previous_standstill(self):
        return self.previous_standstill

    def set_previous_standstill(previous_standstill):
        ...

object was used as the @planning_variable type in Customer since we cannot use Standstill (defined below) as Standstill refer to Customer.

And the shadow side looks like this:

from optapy import planning_entity, inverse_relation_shadow_variable

@planning_entity
class Standstill:
    @inverse_relation_shadow_variable(Customer, source_variable_name = "previous_standstill")
    def get_next_customer(self):
        return self.next_customer

    def set_next_customer(Customer nextCustomer):
        ...

Register this class as a planning entity, otherwise OptaPy won’t detect it and the shadow variable won’t update.

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

3. Anchor shadow variable

An anchor shadow variable is the anchor of a chained variable.

Annotate the anchor property as a @anchor_shadow_variable annotation:

from optapy import planning_entity, anchor_shadow_variable

@planning_entity
class Customer:
    # ...
    @anchor_shadow_variable(Vehicle, source_variable_name = "previous_standstill")
    def get_vehicle(self):
        ...
    def set_vehicle(self, vehicle):
        ...

This class should already be registered as a planning entity. The source_variable_name property is the name of the chained variable on the same entity class.

4. Custom VariableListener

Custom variable listeners are not supported in OptaPy, but will be in a future version.

5. VariableListener triggering order

This section will be added when custom variable listeners are supported in OptaPy.