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 \(S = \{ 0, ..., n - 1 \}\) and a set of actors \(A = \{ 0, ..., m - 1 \}\). In a scene \(s \in S\), a set of actors \(A_s \subseteq A\) plays for \(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 \(a\) is on location, we need to pay the cost \(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 Garcia de la Banda et al. [3]. Suppose that a set of scenes \(Q\) is remaining. A set of actors \(\bigcup_{s \in S \setminus Q} A_s\) already came to the location, and \(\bigcup_{s \in Q} A_s\) is still on location because they need to play on the remaining scenes \(Q\). Therefore, if we shoot a scene \(s \in Q\) next, the set of actors on location will be

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

\[\begin{split}\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.\end{split}\]

Scheduling without Extra Cost

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

\[\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:

\[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.

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 remaining represents the set of remaining scenes. With complement(), we can get the complement of remaining, which is the set of already shot scenes \(S \setminus Q\).

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

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

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

We use a state function on_location to represent \(\left( \bigcup_{s' \in S \setminus Q} A_{s'} \cap \bigcup_{s' \in Q } A_{s'} \right)\) by calling 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 \(\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.

\[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 \(s\) satisfies the condition is unknown, we need to define a transition for each \(s\).

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, scene_to_actors_table[s] == on_location, which corresponds to \(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 forced=True to indicate that this transition is a forced transition.

Ordinarily, DIDPPy takes the minimum (or maximum) 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 \(s_1\) and \(s_2\), when some conditions are satisfied, we can prove that scheduling \(s_1\) first is always better. This can be ensured by preconditions: we can add a precondition to the transition for \(s_2\) that states there is no such \(s_1\) in \(Q\). Alternately, we can use 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 Garcia de la Banda et al. [3] and Kuroiwa and Beck [2].