# Movie Shoot Scheduling¶

## Principles learned¶

• Call an external function

• Set a bound for the external function

• Set a precedence constraint in a list

• Set the number of threads and use multithreading safely in the external function

## Problem¶

We consider a simplified version of the Movie Shoot Scheduling Problem defined by Bomsdorf and Derigs, OR Spectrum. A movie consists of a set of scenes, and each scene takes place for a determined duration in a given location with a set of actors. The order of shooting is not influenced by the order in the final version of the movie, but by economic reasons related to costs of actors and locations. Each actor has a daily cost and for each set of scenes shot in a same location, a fixed cost is associated, depending on the location. There are also precedence constraints between scenes, stating that a scene must be shot before another one. The movie shoot scheduling problem consists in finding the optimal sequence that satisfies the precedence constraints and minimizes the following costs:

• Location cost: Every time a location is visited to shoot a set of scenes, the cost of the location is added, independently of the number of scenes. Only the first visit is not considered in the cost, as every location must be visited at least once.

• Actor cost: An actor must be present for their scenes and has to stay on the set in between. Even when not playing, the actor is paid for these extra days of presence: this is the actor cost.

## Data¶

The instances provided come from the Optimization Hub.

They have been reformatted into the following format:

• Number of actors

• Number of scenes

• Number of locations

• Number of precedences

• Cost for each actor

• Cost for each location

• Duration of each scene

• Location of each scene

• For each scene:

• Presence of each actor

• Precedence between scenes

## Program¶

This LocalSolver model defines a sequence of scenes as a list variable. The i-th element of the list corresponds to the index of the i-th scene to be shot. To ensure that all scenes are scheduled, the size of the list variable is constrained to be equal to the number of scenes. The precedence constraint between two scenes `a` and `b` is obtained with the `indexOf` operator:

```constraint indexOf(sequenceScenes, a) <= indexOf(sequenceScenes, b);
```

As the objective function is rather complex, an external function is used.

• To compute the location cost, we use a variable `nbLocationVisits[k]`, that counts how many times a location `k` was visited to shoot a set of scenes.

• To compute the actor cost, we introduce for each actor `j` two variables: `actorFirstDay[j]` and `actorLastDay[j]`. These variables represent the first and last days of work of the actor. From these variables, we deduce the number of paid days for each actor, which is equal to `actorLastDay[j] - actorFirstDay[j] + 1`. Every actor plays in a given number of scenes that have a fixed duration, so the number of worked days is fixed. Finally the actor cost is deduced from the number of days where actors do not play but are paid, which is the result of `nbPaidDays - nbWorkedDays`.

As the search strategy of LocalSolver is multi-threaded, the member variables of the external function have to be independent between each thread. To compute these costs using an external function, an `O_Call` expression is created.

The external function is provided by the user, so LocalSolver cannot compute its lower and upper bounds. This is why it is useful to modify the `LSExternalContext` to manually set the trivial bounds. As the cost function is always positive, the lower bound is set to 0. The content of the list variable `shootOrder` is given as input of the external function.

The search may be slower in Python and LSP than in C++, Java or C# (see performance issues in Python and LSP for external functions).

Execution:
localsolver movie_shoot_scheduling.lsp inFileName=instances/movie5.txt [lsTimeLimit=] [solFileName=]
```use io;

function input() {
local usage = "Usage: localsolver movie_shoot_scheduling.lsp "
+ "inFileName=inputFile [lsTimeLimit=timeLimit]";

if (inFileName == nil) throw usage;
isActorInScene[j in 0...nbActors][i in 0...nbScenes] = inFile.readInt();
precedence[p in 0...nbPrecedences][q in 0...2] = inFile.readInt();
inFile.close();
computeNbWorkedDays();
}

function computeNbWorkedDays() {
nbWorkedDays[j in 0...nbActors] = sum[i in 0...nbScenes : isActorInScene[j][i]](
sceneDuration[i]);
}

function computeLocationCost(shootOrder) {
// Number of visits per location (group of successive scenes)
nbLocationVisits[k in 0...nbLocations] = 0;
previousLocation = -1;
for [i in 0...nbScenes] {
currentLocation = sceneLocation[shootOrder[i]];
// When we change location, we increment the number of scenes of the new location
if (previousLocation != currentLocation) {
nbLocationVisits[currentLocation] = nbLocationVisits[currentLocation] + 1;
previousLocation = currentLocation;
}
}

locationExtraCost = sum[k in 0...nbLocations](
locationCost[k] * (nbLocationVisits[k] - 1));
return locationExtraCost;
}

function computeActorCost(shootOrder) {
// Compute first and last days of work for each actor
for [j in 0...nbActors] {
hasActorStartingWorking = false;
startDayOfScene = 0;
for [i in 0...nbScenes] {
currentScene = shootOrder[i];
endDayOfScene = startDayOfScene + sceneDuration[currentScene] - 1;
if (isActorInScene[j][currentScene]) {
actorLastDay[j] = endDayOfScene;
if (not(hasActorStartingWorking)) {
hasActorStartingWorking = true;
actorFirstDay[j] = startDayOfScene;
}
}
// The next scene begins the day after the end of the current one
startDayOfScene = endDayOfScene + 1;
}
}

// Compute actor extra cost due to days paid but not worked
actorExtraCost = 0;
for [j in 0...nbActors] {
nbPaidDays = actorLastDay[j] - actorFirstDay[j] + 1;
actorExtraCost += (nbPaidDays - nbWorkedDays[j]) * actorCost[j];
}
return actorExtraCost;
}

/* External function */
function costFunction(context) {
scenes = context;
if (count(scenes) < nbScenes) {
// Infeasible solution if some scenes are missing
return round(pow(10, 6));
}
locationExtraCost = computeLocationCost(scenes);
actorExtraCost = computeActorCost(scenes);
return locationExtraCost + actorExtraCost;
}

/* Declare the optimization model */
function model() {
// A list variable: shootOrder[i] is the index of the ith scene to be shot
shootOrder <- list(nbScenes);

// All scenes must be scheduled
constraint count(shootOrder) == nbScenes;

// Constraint of precedence between scenes
for [i in 0...nbPrecedences]
constraint indexOf(shootOrder, precedence[i])
< indexOf(shootOrder, precedence[i]);

// Minimize external function
func <- intExternalFunction(costFunction);
func.context.lowerBound = 0;
cost <- call(func, shootOrder);
minimize cost;
}

/* Parameterize the solver */
function param() {
if (lsTimeLimit == nil) lsTimeLimit = 20;
}

/* Write the solution in a file in the following format:
* - 1st line: value of the objective;
* - 2nd line: for each i, the index of the ith scene to be shot. */
function output() {
if (solFileName == nil) return;
local solFile = io.openWrite(solFileName);
solFile.println(cost.value);
for [i in shootOrder.value]
solFile.print(i, " ");
solFile.println();
}
```
Execution (Windows)
set PYTHONPATH=%LS_HOME%\bin\python
python movie_shoot_scheduling.py instances\movie5.txt
Execution (Linux)
export PYTHONPATH=/opt/localsolver_12_0/bin/python
python movie_shoot_scheduling.py instances/movie5.txt
```import localsolver
import sys

with open(filename) as f:
return [int(elem) for elem in f.read().split()]

class MssInstance:

#
#
def __init__(self, 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 =  * 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, time_limit):
data = MssInstance(instance_file)

with localsolver.LocalSolver() as ls:
#
# Declare the optimization model
#
model = ls.model

# Decision variable: A list, shoot_order[i] is the index of the ith scene to be shot
shoot_order = model.list(data.nb_scenes)

# All scenes must be scheduled
model.constraint(model.count(shoot_order) == data.nb_scenes)

# Constraint of precedence between scenes
for i in range(data.nb_precedences):
model.constraint(model.index(shoot_order, data.precedences[i])
< model.index(shoot_order, data.precedences[i]))

# Minimize external function
cost_function = CostFunction(data)
func = model.create_int_external_function(cost_function.compute_cost)
func.external_context.lower_bound = 0
cost = func(shoot_order)
model.minimize(cost)
model.close()

# Parameterize the solver
ls.param.time_limit = time_limit if len(sys.argv) >= 4 else 20
ls.solve()

# Write the solution in a file in the following format:
# - 1st line: value of the objective;
# - 2nd line: for each i, the index of the ith scene to be shot.
if len(sys.argv) >= 3:
with open(output_file, 'w') as f:
f.write("%d\n" % cost.value)
for i in shoot_order.value:
f.write("%d " % i)
f.write("\n")

class CostFunction:

def __init__(self, data):
self.data = data

def compute_cost(self, context):
shoot_order = context
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 =  * 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 =  * self.data.nb_actors
actor_last_day =  * 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

if __name__ == '__main__':
if len(sys.argv) < 2:
print("Usage: python movie_shoot_scheduling.py instance_file \
[output_file] [time_limit]")
sys.exit(1)

instance_file = sys.argv
output_file = sys.argv if len(sys.argv) >= 3 else None
time_limit = int(sys.argv) if len(sys.argv) >= 4 else 60
main(instance_file, output_file, time_limit)
```
Compilation / Execution (Windows)
cl /EHsc movie_shoot_scheduling.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver120.lib
movie_shoot_scheduling instances\movie5.txt
Compilation / Execution (Linux)
g++ movie_shoot_scheduling.cpp -I/opt/localsolver_12_0/include -llocalsolver120 -lpthread -o movie_shoot_scheduling
./movie_shoot_scheduling instances/movie5.txt
```#include "localsolver.h"
#include <fstream>
#include <iostream>
#include <limits>
#include <string.h>
#include <vector>
using namespace localsolver;
using namespace std;

class MssInstance {
public:
int nbActors;
int nbScenes;
int nbLocations;
int nbPrecedences;
vector<int> actorCost;
vector<int> locationCost;
vector<int> sceneDuration;
vector<int> sceneLocation;
vector<int> nbWorkedDays;

vector<vector<bool>> isActorInScene;
vector<vector<int>> precedence;

ifstream infile;
infile.open(fileName.c_str());

infile >> nbActors;
infile >> nbScenes;
infile >> nbLocations;
infile >> nbPrecedences;
actorCost.resize(nbActors);
locationCost.resize(nbLocations);
sceneDuration.resize(nbScenes);
sceneLocation.resize(nbScenes);
isActorInScene.resize(nbActors, vector<bool>(nbScenes));
precedence.resize(nbPrecedences, vector<int>(2));

for (int j = 0; j < nbActors; ++j)
infile >> actorCost[j];
for (int k = 0; k < nbLocations; ++k)
infile >> locationCost[k];
for (int i = 0; i < nbScenes; ++i)
infile >> sceneDuration[i];
for (int i = 0; i < nbScenes; ++i)
infile >> sceneLocation[i];
int tmp;
for (int j = 0; j < nbActors; ++j) {
for (int i = 0; i < nbScenes; ++i) {
infile >> tmp;
isActorInScene[j][i] = tmp;
}
}
for (int p = 0; p < nbPrecedences; ++p) {
for (int i = 0; i < 2; ++i)
infile >> precedence[p][i];
}
infile.close();
}

void computeNbWorkedDays() {
nbWorkedDays.resize(nbActors);
for (int j = 0; j < nbActors; ++j) {
nbWorkedDays[j] = 0;
for (int i = 0; i < nbScenes; ++i) {
if (isActorInScene[j][i]) {
nbWorkedDays[j] += sceneDuration[i];
}
}
}
}

public:
MssInstance(const string& fileName) {
computeNbWorkedDays();
}
};

/* External function */
class CostFunction : public LSExternalFunction<lsint> {
private:
const MssInstance* instance;
// here. Each thread must have independant following variables.

// Number of visits per location (group of successive scenes)

// Last day of work for each actor

// Last day of work for each actor

int computeLocationCost(LSCollection shootOrder) {
int previousLocation = -1;
for (int i = 0; i < instance->nbScenes; ++i) {
int currentLocation = instance->sceneLocation[shootOrder[i]];
// When we change location, we increment the number of scenes of the new location
if (previousLocation != currentLocation) {
nbLocationVisits[currentLocation] += 1;
previousLocation = currentLocation;
}
}
int locationExtraCost = 0;
for (int k = 0; k < instance->nbLocations; ++k) {
locationExtraCost += (nbLocationVisits[k] - 1) * instance->locationCost[k];
}
return locationExtraCost;
}

int computeActorCost(LSCollection shootOrder) {
// Compute first and last days of work for each actor
for (int j = 0; j < instance->nbActors; ++j) {
bool hasActorStartedWorking = false;
int startDayOfScene = 0;
for (int i = 0; i < instance->nbScenes; ++i) {
int currentScene = shootOrder[i];
int endDayOfScene = startDayOfScene + instance->sceneDuration[currentScene] - 1;
if (instance->isActorInScene[j][currentScene]) {
actorLastDay[j] = endDayOfScene;
if (!(hasActorStartedWorking)) {
hasActorStartedWorking = true;
actorFirstDay[j] = startDayOfScene;
}
}
// The next scene begins the day after the end of the current one
startDayOfScene = endDayOfScene + 1;
}
}

// Compute actor extra cost due to days paid but not worked
int actorExtraCost = 0;
for (int j = 0; j < instance->nbActors; ++j) {
int nbPaidDays = actorLastDay[j] - actorFirstDay[j] + 1;
actorExtraCost += (nbPaidDays - instance->nbWorkedDays[j]) * instance->actorCost[j];
}
return actorExtraCost;
}

void initStaticVectors() {
nbLocationVisits.clear();
nbLocationVisits.resize(instance->nbLocations, 0);
actorFirstDay.clear();
actorFirstDay.resize(instance->nbActors, 0);
actorLastDay.clear();
actorLastDay.resize(instance->nbActors, 0);
}

public:
CostFunction(const MssInstance* instance) : instance(instance) {}

lsint call(const LSExternalArgumentValues& argumentValues) {
LSCollection shootOrder = argumentValues.getCollectionValue(0);
if (shootOrder.count() < instance->nbScenes) {
// Infeasible solution if some scenes are missing
return numeric_limits<int>::max();
}

initStaticVectors();
int locationExtraCost = computeLocationCost(shootOrder);
int actorExtraCost = computeActorCost(shootOrder);
return locationExtraCost + actorExtraCost;
}
};

class MovieShootScheduling {
private:
// LocalSolver
LocalSolver localsolver;

// Instance data
const MssInstance* instance;

// Decision variable
LSExpression shootOrder;

// Objective
LSExpression callCostFunc;

public:
MovieShootScheduling(const MssInstance* mssi) { instance = mssi; }

void solve(int limit) {
// Declare the optimization model
LSModel model = localsolver.getModel();

// A list variable: shootOrder[i] is the index of the ith scene to be shot
shootOrder = model.listVar(instance->nbScenes);

// All scenes must be scheduled
model.constraint(model.count(shootOrder) == instance->nbScenes);

// Constraint of precedence between scenes
for (int p = 0; p < instance->nbPrecedences; ++p)
model.constraint(model.indexOf(shootOrder, instance->precedence[p]) <
model.indexOf(shootOrder, instance->precedence[p]));

// Minimize external function
CostFunction costObject(instance);
LSExpression costFunc = model.createExternalFunction(&costObject);
costFunc.getExternalContext().setIntLowerBound(0);
callCostFunc = costFunc(shootOrder);
model.minimize(callCostFunc);

model.close();

// Parameterize the solver
localsolver.getParam().setTimeLimit(limit);

localsolver.solve();
}

/* Write the solution in a file in the following format:
* - 1st line: value of the objective;
* - 2nd line: for each i, the index of the ith scene to be shot. */
void writeSolution(const string& fileName) {
ofstream outfile;
outfile.open(fileName.c_str());
outfile << callCostFunc.getIntValue() << endl;
LSCollection shootOrderCollection = shootOrder.getCollectionValue();
for (int i = 0; i < instance->nbScenes; ++i) {
outfile << shootOrderCollection[i] << " ";
}
outfile << endl;
}
};

int main(int argc, char** argv) {
if (argc < 2) {
cerr << "Usage: movie_shoot_scheduling inputFile [outputFile] [timeLimit]" << endl;
return 1;
}
const char* instanceFile = argv;
const char* solFile = argc > 2 ? argv : NULL;
const char* strTimeLimit = argc > 3 ? argv : "20";
MssInstance instance(instanceFile);
MovieShootScheduling model(&instance);
try {
model.solve(atoi(strTimeLimit));
if (solFile != NULL)
model.writeSolution(solFile);
return 0;
} catch (const exception& e) {
cerr << "An error occurred: " << e.what() << endl;
return 1;
}
}
```
Compilation / Execution (Windows)
copy %LS_HOME%\bin\localsolvernet.dll .
csc MovieShootScheduling.cs /reference:localsolvernet.dll
MovieShootScheduling instances\movie5.txt
```using System;
using System.IO;
using localsolver;

public class MssInstance
{
public int nbActors;
public int nbScenes;
public int nbLocations;
public int nbPrecedences;
public int[] actorCost;
public int[] locationCost;
public int[] sceneDuration;
public int[] sceneLocation;
public int[] nbWorkedDays;

public bool[,] isActorInScene;
public int[,] precedence;

public MssInstance(string fileName)
{
ComputeNbWorkedDays();
}

{
{
string[] line;
actorCost = new int[nbActors];
locationCost = new int[nbLocations];
sceneDuration = new int[nbScenes];
sceneLocation = new int[nbScenes];
isActorInScene = new bool[nbActors, nbScenes];
precedence = new int[nbPrecedences, 2];

for (int j = 0; j < nbActors; ++j)
actorCost[j] = int.Parse(line[j]);
for (int k = 0; k < nbLocations; ++k)
locationCost[k] = int.Parse(line[k]);
for (int i = 0; i < nbScenes; ++i)
sceneDuration[i] = int.Parse(line[i]);
for (int i = 0; i < nbScenes; ++i)
sceneLocation[i] = int.Parse(line[i]);
for (int j = 0; j < nbActors; ++j)
{
for (int i = 0; i < nbScenes; ++i)
isActorInScene[j, i] = Convert.ToBoolean(int.Parse(line[i]));
}
for (int p = 0; p < nbPrecedences; ++p)
{
for (int i = 0; i < 2; ++i)
precedence[p, i] = int.Parse(line[i]);
}
}
}

private void ComputeNbWorkedDays()
{
nbWorkedDays = new int[nbActors];
for (int j = 0; j < nbActors; ++j)
{
nbWorkedDays[j] = 0;
for (int i = 0; i < nbScenes; ++i)
{
if (isActorInScene[j, i])
nbWorkedDays[j] += sceneDuration[i];
}
}
}
}

/* External function */
public class CostFunction
{
MssInstance instance;

// here. Each thread must have independant following variables.

// Number of visits per location (group of successive scenes)
static int[] nbLocationVisits;

// First day of work for each actor
static int[] actorFirstDay;

// Last day of work for each actor
static int[] actorLastDay;

public CostFunction(MssInstance instance)
{
this.instance = instance;
}

public long Call(LSExternalArgumentValues argumentValues)
{
LSCollection shootOrder = argumentValues.GetCollectionValue(0);
int shootOrderLength = shootOrder.Count();
if (shootOrderLength < instance.nbScenes)
{
// Infeasible solution if some scenes are missing
return Int32.MaxValue;
}

InitStaticVectors();
ResetStaticVectors();
long[] shootOrderArray = new long[shootOrderLength];
shootOrder.CopyTo(shootOrderArray);

int locationExtraCost = ComputeLocationCost(shootOrderArray);
int actorExtraCost = ComputeActorCost(shootOrderArray);
return locationExtraCost + actorExtraCost;
}

private int ComputeLocationCost(long[] shootOrderArray)
{
int previousLocation = -1;
for (int i = 0; i < instance.nbScenes; ++i)
{
int currentLocation = instance.sceneLocation[shootOrderArray[i]];
// When we change location, we increment the number of scenes of the new location
if (previousLocation != currentLocation)
{
nbLocationVisits[currentLocation] += 1;
previousLocation = currentLocation;
}
}
int locationExtraCost = 0;
for (int k = 0; k < instance.nbLocations; ++k)
locationExtraCost += (nbLocationVisits[k] - 1) * instance.locationCost[k];
return locationExtraCost;
}

private int ComputeActorCost(long[] shootOrderArray)
{
// Compute first and last days of work for each actor
for (int j = 0; j < instance.nbActors; ++j)
{
bool hasActorStartedWorking = false;
int startDayOfScene = 0;
for (int i = 0; i < instance.nbScenes; ++i)
{
int currentScene = Convert.ToInt32(shootOrderArray[i]);
int endDayOfScene = startDayOfScene + instance.sceneDuration[currentScene] - 1;
if (instance.isActorInScene[j, currentScene])
{
actorLastDay[j] = endDayOfScene;
if (!(hasActorStartedWorking))
{
hasActorStartedWorking = true;
actorFirstDay[j] = startDayOfScene;
}
}
// The next scene begins the day after the end of the current one
startDayOfScene = endDayOfScene + 1;
}
}

// Compute actor extra cost due to days paid but not worked
int actorExtraCost = 0;
for (int j = 0; j < instance.nbActors; ++j)
{
int nbPaidDays = actorLastDay[j] - actorFirstDay[j] + 1;
actorExtraCost += (nbPaidDays - instance.nbWorkedDays[j]) * instance.actorCost[j];
}
return actorExtraCost;
}

void InitStaticVectors()
{
if (nbLocationVisits == null)
nbLocationVisits = new int[instance.nbLocations];
if (actorFirstDay == null)
actorFirstDay = new int[instance.nbActors];
if (actorLastDay == null)
actorLastDay = new int[instance.nbActors];
}

void ResetStaticVectors()
{
for (int k = 0; k < instance.nbLocations; ++k)
nbLocationVisits[k] = 0;
for (int j = 0; j < instance.nbActors; ++j)
{
actorFirstDay[j] = 0;
actorLastDay[j] = 0;
}
}
}

public class MovieShootScheduling : IDisposable
{
// LocalSolver
LocalSolver localsolver;

// Instance data
MssInstance instance;

// Decision variable
LSExpression shootOrder;

// Objective
LSExpression callCostFunc;

public MovieShootScheduling(MssInstance instance)
{
this.localsolver = new LocalSolver();
this.instance = instance;
}

public void Dispose()
{
if (localsolver != null)
localsolver.Dispose();
}

void Solve(int limit)
{
// Declare the optimization model
LSModel model = localsolver.GetModel();

// A list variable: shootOrder[i] is the index of the ith scene to be shot
shootOrder = model.List(instance.nbScenes);

// All scenes must be scheduled
model.Constraint(model.Count(shootOrder) == instance.nbScenes);

// Constraint of precedence between scenes
for (int p = 0; p < instance.nbPrecedences; ++p)
model.Constraint(
model.IndexOf(shootOrder, instance.precedence[p, 0])
< model.IndexOf(shootOrder, instance.precedence[p, 1])
);

// Minimize external function
CostFunction costObject = new CostFunction(instance);
LSIntExternalFunction func = new LSIntExternalFunction(costObject.Call);
LSExpression costFunc = model.CreateIntExternalFunction(func);
costFunc.GetExternalContext().SetIntLowerBound(0);
callCostFunc = model.Call(costFunc, shootOrder);
model.Minimize(callCostFunc);

model.Close();

// Parameterize the solver
localsolver.GetParam().SetTimeLimit(limit);

localsolver.Solve();
}

/* Write the solution in a file in the following format:
* - 1st line: value of the objective;
* - 2nd line: for each i, the index of the ith scene to be shot. */
void WriteSolution(string fileName)
{
using (StreamWriter output = new StreamWriter(fileName))
{
output.WriteLine(callCostFunc.GetIntValue());
LSCollection shootOrderCollection = shootOrder.GetCollectionValue();
for (int i = 0; i < instance.nbScenes; ++i)
output.Write(shootOrderCollection.Get(i) + " ");
output.WriteLine();
}
}

public static void Main(string[] args)
{
if (args.Length < 1)
{
Console.WriteLine("Usage: MovieShootScheduling inputFile [solFile] [timeLimit]");
Environment.Exit(1);
}
string instanceFile = args;
string outputFile = args.Length > 1 ? args : null;
string strTimeLimit = args.Length > 2 ? args : "20";
MssInstance instance = new MssInstance(instanceFile);
using (MovieShootScheduling model = new MovieShootScheduling(instance))
{
model.Solve(int.Parse(strTimeLimit));
if (outputFile != null)
model.WriteSolution(outputFile);
}
}
}
```
Compilation / Execution (Windows)
javac MovieShootScheduling.java -cp %LS_HOME%\bin\localsolver.jar
java -cp %LS_HOME%\bin\localsolver.jar;. MovieShootScheduling instances\movie5.txt
Compilation / Execution (Linux)
javac MovieShootScheduling.java -cp /opt/localsolver_12_0/bin/localsolver.jar
java -cp /opt/localsolver_12_0/bin/localsolver.jar:. MovieShootScheduling instances/movie5.txt
```import java.util.Scanner;
import java.io.*;
import localsolver.*;

public class MovieShootScheduling {

private static class MssInstance {

int nbActors;
int nbScenes;
int nbLocations;
int nbPrecedences;
int[] actorCost;
int[] locationCost;
int[] sceneDuration;
int[] sceneLocation;
int[] nbWorkedDays;

int[][] precedences;
boolean[][] isActorInScene;

/* Constructor */
private MssInstance(String fileName) throws IOException {
computeNbWorkedDays();
}

private void readInput(String fileName) throws IOException {
try (Scanner input = new Scanner(new File(fileName))) {
nbActors = input.nextInt();
nbScenes = input.nextInt();
nbLocations = input.nextInt();
nbPrecedences = input.nextInt();
actorCost = new int[nbActors];
locationCost = new int[nbLocations];
sceneDuration = new int[nbScenes];
sceneLocation = new int[nbScenes];
isActorInScene = new boolean[nbActors][nbScenes];
precedences = new int[nbPrecedences];

for (int j = 0; j < nbActors; ++j)
actorCost[j] = input.nextInt();
for (int k = 0; k < nbLocations; ++k)
locationCost[k] = input.nextInt();
for (int i = 0; i < nbScenes; ++i)
sceneDuration[i] = input.nextInt();
for (int i = 0; i < nbScenes; ++i)
sceneLocation[i] = input.nextInt();
for (int j = 0; j < nbActors; ++j) {
for (int i = 0; i < nbScenes; ++i) {
int tmp = input.nextInt();
isActorInScene[j][i] = (tmp == 1);
}
}
for (int p = 0; p < nbPrecedences; ++p) {
for (int i = 0; i < 2; ++i) {
precedences[p][i] = input.nextInt();
}
}
}
}

private void computeNbWorkedDays() {
nbWorkedDays = new int[nbActors];
for (int j = 0; j < nbActors; ++j) {
nbWorkedDays[j] = 0;
for (int i = 0; i < nbScenes; ++i) {
if (isActorInScene[j][i]) {
nbWorkedDays[j] += sceneDuration[i];
}
}
}
}
}

/* External function */
private static class CostFunction implements LSIntExternalFunction {

private final MssInstance instance;

// Each thread must have independant following variables.

// Number of visits per location (group of successive scenes)

// First day of work for each actor

// Last day of work for each actor

/* Constructor */
private CostFunction(MssInstance instance) {
this.instance = instance;
this.nbLocationVisits = ThreadLocal.withInitial(() -> new int[instance.nbLocations]);
this.actorFirstDay = ThreadLocal.withInitial(() -> new int[instance.nbActors]);
this.actorLastDay = ThreadLocal.withInitial(() -> new int[instance.nbActors]);
}

@Override
public long call(LSExternalArgumentValues argumentValues) {
LSCollection shootOrder = argumentValues.getCollectionValue(0);
int shootOrderLength = shootOrder.count();
if (shootOrderLength < instance.nbScenes) {
// Infeasible solution if some scenes are missing
return Integer.MAX_VALUE;
}

resetVectors();
long[] shootOrderArray = new long[shootOrderLength];
shootOrder.copyTo(shootOrderArray);

int locationExtraCost = computeLocationCost(shootOrderArray);
int actorExtraCost = computeActorCost(shootOrderArray);
return locationExtraCost + actorExtraCost;
}

private int computeLocationCost(long[] shootOrderArray) {
int previousLocation = -1;
for (int i = 0; i < instance.nbScenes; ++i) {
int currentLocation = instance.sceneLocation[(int) shootOrderArray[i]];
// When we change location, we increment the number of visits of the new location
if (previousLocation != currentLocation) {
nbLocationVisits.get()[currentLocation] += 1;
previousLocation = currentLocation;
}
}
int locationExtraCost = 0;
for (int k = 0; k < instance.nbLocations; ++k) {
locationExtraCost += (nbLocationVisits.get()[k] - 1) * instance.locationCost[k];
}
return locationExtraCost;
}

private int computeActorCost(long[] shootOrderArray) {
// Compute first and last days of work for each actor
for (int j = 0; j < instance.nbActors; ++j) {
boolean hasActorStartedWorking = false;
int startDayOfScene = 0;
for (int i = 0; i < instance.nbScenes; ++i) {
int currentScene = (int) shootOrderArray[i];
int endDayOfScene = startDayOfScene + instance.sceneDuration[currentScene] - 1;
if (instance.isActorInScene[j][currentScene]) {
actorLastDay.get()[j] = endDayOfScene;
if (!hasActorStartedWorking) {
hasActorStartedWorking = true;
actorFirstDay.get()[j] = startDayOfScene;
}
}
// The next scene begins the day after the end of the current one
startDayOfScene = endDayOfScene + 1;
}
}

// Compute actor extra cost due to days paid but not worked
int actorExtraCost = 0;
for (int j = 0; j < instance.nbActors; ++j) {
int nbPaidDays = actorLastDay.get()[j] - actorFirstDay.get()[j] + 1;
actorExtraCost += (nbPaidDays - instance.nbWorkedDays[j]) * instance.actorCost[j];
}
return actorExtraCost;
}

private void resetVectors() {
for (int j = 0; j < instance.nbActors; ++j) {
actorFirstDay.get()[j] = 0;
actorLastDay.get()[j] = 0;
}
for (int k = 0; k < instance.nbLocations; ++k) {
nbLocationVisits.get()[k] = 0;
}
}
}

private static class MSSProblem {

// LocalSolver
private final LocalSolver localsolver;

// Instance data
private final MssInstance instance;

// Decision variable
private LSExpression shootOrder;

// Objective
private LSExpression callCostFunc;

private MSSProblem(LocalSolver localsolver, MssInstance instance) {
this.localsolver = localsolver;
this.instance = instance;
}

private void solve(int limit) {
// Declare the optimization model
LSModel model = localsolver.getModel();

// A list variable: shootOrder[i] is the index of the ith scene to be shot
shootOrder = model.listVar(instance.nbScenes);

// Every scene must be scheduled
model.constraint(model.eq(model.count(shootOrder), instance.nbScenes));

// Constraint of precedence between scenes
for (int p = 0; p < instance.nbPrecedences; ++p)
model.constraint(model.lt(model.indexOf(shootOrder, instance.precedences[p]),
model.indexOf(shootOrder, instance.precedences[p])));

// Minimize external function
CostFunction costObject = new CostFunction(instance);
LSExpression costFunc = model.createIntExternalFunction(costObject);
costFunc.getExternalContext().setLowerBound(0);
callCostFunc = model.call(costFunc, shootOrder);
model.minimize(callCostFunc);

model.close();

// Parameterize the solver
localsolver.getParam().setTimeLimit(limit);

localsolver.solve();
}

/*
* Write the solution in a file in the following format:
* - 1st line: value of the objective
* - 2nd line: for each i, the index of the ith scene to be shot
*/
void writeSolution(String fileName) throws IOException {
try (PrintWriter output = new PrintWriter(new FileWriter(fileName))) {
output.println(callCostFunc.getIntValue());
LSCollection shootOrderCollection = shootOrder.getCollectionValue();
for (int i = 0; i < instance.nbScenes; ++i) {
output.print(shootOrderCollection.get(i) + " ");
}
output.println();
}
}
}

public static void main(String[] args) {
if (args.length < 1) {
System.err.println("Usage: MovieShootScheduling inputFile [outputFile] [timeLimit]");
System.exit(1);
}

String instanceFile = args;
String outputFile = args.length > 1 ? args : null;
String strTimeLimit = args.length > 2 ? args : "5";
try (LocalSolver localsolver = new LocalSolver()) {
MssInstance instance = new MssInstance(instanceFile);
MSSProblem model = new MSSProblem(localsolver, instance);
model.solve(Integer.parseInt(strTimeLimit));
if (outputFile != null) {
model.writeSolution(outputFile);
}
} catch (Exception ex) {
System.err.println(ex);
ex.printStackTrace();
System.exit(1);
}
}
}
```