Forced Transitions
==================

In this tutorial, we will see how to use forced transitions using the talent scheduling problem as an example.

Talent Scheduling
-----------------

In a talent scheduling problem, we are given a set of scenes :math:`S = \{ 0, ..., n - 1 \}` and a set of actors :math:`A = \{ 0, ..., m - 1 \}`.
In a scene :math:`s \in S`, a set of actors :math:`A_s \subseteq A` plays for :math:`d_s` days.
An actor comes to the location when the first scene he or she plays starts and leaves when the last scene he or she plays ends.
For each day actor :math:`a` is on location, we need to pay the cost :math:`c_a`.
We want to find a sequence of scenes to shoot such that the total cost is minimized.

DP Formulation
--------------

The DP formulation is based on :cite:t:`GarciaDeLaBanda2011`.
Suppose that a set of scenes :math:`Q` is remaining.
A set of actors :math:`\bigcup_{s \in S \setminus Q} A_s` already came to the location, and :math:`\bigcup_{s \in Q} A_s` is still on location because they need to play on the remaining scenes :math:`Q`.
Therefore, if we shoot a scene :math:`s \in Q` next, the set of actors on location will be

.. math::

    L(s, Q) = A_s \cup \left( \bigcup_{s' \in S \setminus Q} A_{s'} \cap \bigcup_{s' \in Q } A_{s'}  \right).

We need to pay the cost :math:`d_s \sum_{a \in L(s, Q)} c_a` when shooting scene :math:`s`.
Once we shot scene :math:`s`, the remaining problem is to decide the order of the remaining scenes :math:`Q \setminus \{ s \}`.
Therefore, a state is defined by the set of remaining scenes :math:`Q`, and the minimum cost to shoot :math:`Q` is represented by :math:`V(Q)`.
Because :math:`A_s`, actors who play in scence :math:`s`, are always on location when :math:`s` is shot, :math:`\sum_{s \in Q} d_s \sum_{a \in A_s} c_a` is a lower bound on :math:`V(Q)`.
We have the following DP formulation.

.. math::

    \text{compute } & V(S) \\
    & V(Q) = \begin{cases}
        \min\limits_{s \in Q} d_s \sum\limits_{a \in L(s, Q)} c_a + V(Q \setminus \{ s \}) & \text{if } Q \neq \emptyset \\
        0 & \text{if } Q = \emptyset
    \end{cases} \\
    & V(Q) \geq \sum_{s \in Q} d_s \sum_{a \in A_s} c_a.

Scheduling without Extra Cost
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

If :math:`A_s`, the set of actors that play in scence :math:`s`, is equivalent to the set of actors currently on location, we can shoot :math:`s` with the minimum cost:
we just need to pay for the actors who play in :math:`s`.
We should always shoot such a scene first.
In state :math:`Q`, the set of actors on location is

.. math::

    \bigcup_{s \in S \setminus Q} A_{s} \cap \bigcup_{s \in Q} A_{s}.

Therefore, we have the following optimal transition under certain conditions:

.. math::

    V(Q) = d_s \sum\limits_{a \in A_s} c_a + V(Q \setminus \{ s \}) \text{ if } s \in Q \land A_s = \bigcup_{s' \in S \setminus Q} A_{s'} \cap \bigcup_{s' \in Q} A_{s'}.

If multiple scenes satisfy the condition, we can shoot any of them.
This equation helps a solver because it tells that other scenes are not needed to be considered.

Modeling in DIDPPy
------------------

To model the above equation, we can use forced transitions.
Before defining forced transitions, let's model the other parts of the formulation.

.. code-block:: python

    import didppy as dp

    # Number of scenes
    n = 4
    # Number of actors
    m = 4
    # Duration of scenes
    d = [1, 1, 1, 1]
    # Costs of actors
    c = [1, 3, 1, 2]
    # Actors in each scene
    scene_to_actors = [[0, 1, 3], [1, 2], [0, 2, 3], [0, 1, 2]]

    model = dp.Model()

    scene = model.add_object_type(number=n)
    actor = model.add_object_type(number=m)

    # Q
    remaining = model.add_set_var(object_type=scene, target=list(range(n)))

    scene_to_actors_table = model.add_set_table(scene_to_actors, object_type=scene)
    actor_to_cost = model.add_int_table(c)

    # Precompute the minimum cost of each scene
    scene_to_min_cost = model.add_int_table(
        [d[s] * sum(c[a] for a in scene_to_actors[s]) for s in range(n)]
    )

    came_to_location = scene_to_actors_table.union(remaining.complement())
    standby = scene_to_actors_table.union(remaining)
    on_location = model.add_set_state_fun(came_to_location & standby)

    for s in range(n):
        on_location_s = scene_to_actors_table[s] | on_location

        shoot = dp.Transition(
            name="shoot {}".format(s),
            cost=d[s] * actor_to_cost[on_location_s] + dp.IntExpr.state_cost(),
            effects=[(remaining, remaining.remove(s))],
            preconditions=[remaining.contains(s)],
        )
        model.add_transition(shoot)

    model.add_base_case([remaining.is_empty()])

    model.add_dual_bound(scene_to_min_cost[remaining])

The state variable :code:`remaining` represents the set of remaining scenes.
With :meth:`~didppy.StateVar.complement`, we can get the complement of :code:`remaining`, which is the set of already shot scenes :math:`S \setminus Q`.

We define a set table :code:`scene_to_actors_table` to represent the set of actors in each scene using :meth:`~didppy.Model.add_set_table`.
When defining a set table, we can use a :class:`list` of :class:`list` or :class:`set`, but we need to specify the object type using :code:`object_type` argument.
Alternately, we can use a list of :class:`~didppy.SetConst`, which does not requore :code:`object_type` as it is specified when created by :meth:`~didppy.Model.create_set_const`.

By using the :meth:`~didppy.SetTable1D.union` method of a table, we can get the union of sets in the table whose indices are elements in the set (:class:`~didppy.SetVar`, :class:`~didppy.SetExpr`, or :class:`~didppy.SetConst`) given as an argument.
Therefore, :code:`scene_to_actors_table.union(remaining)` corresponds to :math:`\bigcup_{s \in Q} A_s`.

The union and intersection of two sets can be represented by the bitwise OR operator :code:`|` and AND operator :code:`&`.
In addition, the operators :code:`-` and :code:`^` can be used to take the difference and symmetric difference of two sets, respectively.

We use a state function :code:`on_location` to represent :math:`\left( \bigcup_{s' \in S \setminus Q} A_{s'} \cap \bigcup_{s' \in Q } A_{s'}  \right)` by calling :meth:`~didppy.Model.add_set_state_fun`.
A state function is a function of a state defined by an expression.
It is useful to represent information implied by state variables.
A solver can cache the value of a state function to avoid redundant computation if it is used in multiple places.
Computing :math:`\left( \bigcup_{s' \in S \setminus Q} A_{s'} \cap \bigcup_{s' \in Q } A_{s'}  \right)` requires linear time in the number of scenes, which is not cheap, so it is better to use a state function in this case.

Defining Forced Transitions
~~~~~~~~~~~~~~~~~~~~~~~~~~~

Now, let's model the following equation using forced transitions.

.. math::

    V(Q) = d_s \sum\limits_{a \in A_s} c_a + V(Q \setminus \{ s \}) \text{ if } s \in Q \land A_s = \bigcup_{s' \in S \setminus Q} A_{s'} \cap \bigcup_{s' \in Q} A_{s'}.

Because which :math:`s` satisfies the condition is unknown, we need to define a transition for each :math:`s`.

.. code-block:: python

    for s in range(n):
        shoot = dp.Transition(
            name="forced shoot {}".format(s),
            cost=scene_to_min_cost[s] + dp.IntExpr.state_cost(),
            effects=[(remaining, remaining.remove(s))],
            preconditions=[
                remaining.contains(s),
                scene_to_actors_table[s] == on_location
            ],
        )
        model.add_transition(shoot, forced=True)

Now, we have an additional precondition, :code:`scene_to_actors_table[s] == on_location`, which corresponds to :math:`A_s = \bigcup_{s' \in S \setminus Q} A_{s'} \cap \bigcup_{s' \in Q} A_{s'}`.
When registering this transition to the model, we use the argument :code:`forced=True` to indicate that this transition is a forced transition.

Ordinarily, DIDPPy takes the minimum (or maximum) :code:`cost` over all transitions whose preconditions are satisfied. 
However, if preconditions of a forced transition are satisfied, DIDPPy ignores other transitions and only considers the forced transition.
If multiple forced transitions are available, DIDPPy selects the one first added to the model.
Therefore, **the order to add forced transitions does matter**.

Further optimization
--------------------

We can further optimize this DP model by considering dominance relations between scenes:
given two scenes :math:`s_1` and :math:`s_2`, when some conditions are satisfied, we can prove that scheduling :math:`s_1` first is always better.
This can be ensured by preconditions: we can add a precondition to the transition for :math:`s_2` that states there is no such :math:`s_1` in :math:`Q`.
Alternately, we can use :doc:`transition dominance <transition-dominance>` to define a dominance relation between transitions.

We do not go into details here.
If you are interested in this topic, please refer :cite:t:`GarciaDeLaBanda2011` and :cite:t:`DIDPAnytime`.