问题描述¶
我们考虑由 Bomsdorf and Derigs, OR Spectrum 定义的电影拍摄调度问题的简化版本。一部电影由一组场景组成，每个场景在给定的地点以一组演员持续一段确定的时长。我们必须确定场景的拍摄顺序，该顺序不一定与它们在最终电影中的顺序相同。然而，存在紧前约束，规定某些场景必须在其他场景之前拍摄。
问题的目标是找到一个使总成本最小化的序列，总成本是演员成本和地点成本之和。事实上，演员不仅需要出现在其每个场景中，还需要出现在其场景之间。他们必须为其在现场的每个额外在场日获得报酬。此外，每当访问某个地点以拍摄一组场景时，都需要支付地点成本，无论场景数量如何。由于我们必须至少访问每个地点一次，因此我们忽略首次访问的成本。
学习要点¶
- 使用列表变量表示拍摄顺序。
- 使用
index获取场景的位置，并添加紧前约束。 - 使用
create_int_external_function将演员和地点成本计算接入目标表达式。
数据¶
我们提供的电影拍摄调度问题实例来自 Optimization Hub。其格式如下：
- 演员数
- 场景数
- 地点数
- 紧前关系数
- 每个演员的成本
- 每个地点的成本
- 每个场景的时长
- 每个场景的地点
- 对每个场景，每个演员的出场情况
- 场景之间的紧前关系
建模思路¶
OptAgent 模型使用一个列表变量表示场景的拍摄顺序，约束其长度等于场景数，使每个场景恰好出现一次。通过 model.index 获取指定场景的位置，并约束前驱场景的位置小于后继场景的位置。
CostFunction.compute_cost 从回调参数读取候选场景序列，计算演员的额外在场成本与地点的重复访问成本，返回整数总成本。模型使用 create_int_external_function 注册该函数，再将它应用于列表变量，最小化得到的调用表达式。
调用 solve(model, time_limit_s=...) 后，可以从列表表达式读取拍摄顺序，从目标表达式读取成本。读取值前应确认结果具有可行解。
Python 实现¶
from pathlib import Path
import sys
from optagent import OptModel, solve
def read_integers(filename):
return [int(elem) for elem in Path(filename).read_text(encoding="utf-8").split()]
class MssInstance:
#
# Read instance data
#
def __init__(self, filename):
file_it = iter(read_integers(filename))
self.nb_actors = next(file_it)
self.nb_scenes = next(file_it)
self.nb_locations = next(file_it)
self.nb_precedences = next(file_it)
self.actor_cost = [next(file_it) for i in range(self.nb_actors)]
self.location_cost = [next(file_it) for i in range(self.nb_locations)]
self.scene_duration = [next(file_it) for i in range(self.nb_scenes)]
self.scene_location = [next(file_it) for i in range(self.nb_scenes)]
self.is_actor_in_scene = [[next(file_it) for i in range(self.nb_scenes)]
for i in range(self.nb_actors)]
self.precedences = [[next(file_it) for i in range(2)]
for i in range(self.nb_precedences)]
self.actor_nb_worked_days = self._compute_nb_worked_days()
def _compute_nb_worked_days(self):
actor_nb_worked_days = [0] * self.nb_actors
for a in range(self.nb_actors):
for s in range(self.nb_scenes):
if self.is_actor_in_scene[a][s]:
actor_nb_worked_days[a] += self.scene_duration[s]
return actor_nb_worked_days
def main(instance_file, output_file=None, time_limit=60):
data = MssInstance(instance_file)
model = OptModel()
# shoot_order[i] is the scene index shot at position i.
shoot_order = model.list(data.nb_scenes)
model.constraint(
model.count(shoot_order) == data.nb_scenes
)
# Preserve the original precedence constraints through list index lookup.
for before, after in data.precedences:
model.constraint(
model.index(shoot_order, before) < model.index(shoot_order, after),
)
# Evaluate the scene order with an integer-valued external cost function.
cost_function = CostFunction(data)
external_cost = model.create_int_external_function(cost_function.compute_cost)
cost = external_cost(shoot_order)
model.minimize(cost)
solution = solve(model, time_limit_s=float(time_limit))
order = list(shoot_order.value)
print(
f"Actors = {data.nb_actors}; Scenes = {data.nb_scenes}; "
f"Locations = {data.nb_locations}; Cost = {cost.value}; "
f"Status = {solution.feasible}"
)
print("Shoot order:", order)
if output_file is not None:
Path(output_file).write_text(
f"{cost.value}\n" + " ".join(map(str, order)) + "\n",
encoding="utf-8",
)
return solution
class CostFunction:
def __init__(self, data):
self.data = data
def compute_cost(self, context):
shoot_order = context[0]
if len(shoot_order) < self.data.nb_scenes:
# Infeasible solution if some scenes are missing
return sys.maxsize
location_extra_cost = self._compute_location_cost(shoot_order)
actor_extra_cost = self._compute_actor_cost(shoot_order)
return location_extra_cost + actor_extra_cost
def _compute_location_cost(self, shoot_order):
nb_location_visits = [0] * self.data.nb_locations
previous_location = -1
for i in range(self.data.nb_scenes):
current_location = self.data.scene_location[shoot_order[i]]
# When we change location, we increment the number of scenes of the new location
if previous_location != current_location:
nb_location_visits[current_location] += 1
previous_location = current_location
location_extra_cost = sum(cost * (nb_visits - 1)
for cost, nb_visits in zip(self.data.location_cost, nb_location_visits))
return location_extra_cost
def _compute_actor_cost(self, shoot_order):
# Compute first and last days of work for each actor
actor_first_day = [0] * self.data.nb_actors
actor_last_day = [0] * self.data.nb_actors
for j in range(self.data.nb_actors):
has_actor_started_working = False
start_day_of_scene = 0
for i in range(self.data.nb_scenes):
current_scene = shoot_order[i]
end_day_of_scene = start_day_of_scene \
+ self.data.scene_duration[current_scene] - 1
if self.data.is_actor_in_scene[j][current_scene]:
actor_last_day[j] = end_day_of_scene
if not has_actor_started_working:
has_actor_started_working = True
actor_first_day[j] = start_day_of_scene
# The next scene begins the day after the end of the current one
start_day_of_scene = end_day_of_scene + 1
# Compute actor extra cost due to days paid but not worked
actor_extra_cost = 0
for j in range(self.data.nb_actors):
nb_paid_days = actor_last_day[j] - actor_first_day[j] + 1
actor_extra_cost += (nb_paid_days - self.data.actor_nb_worked_days[j]) \
* self.data.actor_cost[j]
return actor_extra_cost
本地运行¶
以下代码格演示如何调用 OptAgent 的电影拍摄调度模型。
INSTANCE_DIR = Path.cwd() / "instances"
print("Instances:", INSTANCE_DIR)
solution_movie5 = main(INSTANCE_DIR / "movie5.txt", time_limit=1)
solution_movie10 = main(INSTANCE_DIR / "movie10.txt", time_limit=1)