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

../_images/movie_shoot_scheduling.png

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, independantly 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.
Download the example


Data

The instances provided come from the Optimization Hub.

They have been reformatted into the following format:

  • Number of scenes
  • Number of actors
  • 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=]
/********** movie_shoot_scheduling.lsp **********/
use io;
use ls;

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

    if (inFileName == nil) throw usage;
    local inFile = io.openRead(inFileName);
    nbActors = inFile.readInt();
    nbScenes = inFile.readInt();
    nbLocations = inFile.readInt();
    nbPrecedences = inFile.readInt();
    actorCost[i in 0..nbActors-1] = inFile.readInt();
    locationCost[i in 0..nbLocations-1] = inFile.readInt();
    sceneDuration[i in 0..nbScenes-1] = inFile.readInt();
    sceneLocation[i in 0..nbScenes-1] = inFile.readInt();
    for [i in 0..nbActors-1]
        isActorInScene[i][j in 0..nbScenes-1] = inFile.readInt();
    for [i in 0..nbPrecedences-1]
        precedence[i][j in 0..1] = inFile.readInt();
    inFile.close();
    computeNbWorkedDays();
}

function computeNbWorkedDays() {
    nbWorkedDays[i in 0..nbActors-1] = 0;
    for [j in 0..nbActors-1] {
        for [i in 0..nbScenes-1] {
            if (isActorInScene[j][i]) {
                nbWorkedDays[j] += sceneDuration[i];
            }
        }
    }
}

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

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

function computeActorCost(shootOrder) {
    for [j in 0..nbActors-1] {
        hasActorStartingWorking = false;
        startDayOfScene = 0;
        for [i in 0..nbScenes-1] {
            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-1] {
        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 shoots are missing
        return round(pow(10, 6));
    }
    locationExtraCost = computeLocationCost(scenes);
    actorExtraCost = computeActorCost(scenes);
    return locationExtraCost + actorExtraCost;
}

function model() {
    // Decision variable: a list, shootOrder[i] is the index of the i-th 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-1] {
        constraint indexOf(shootOrder, precedence[i][0]) < indexOf(shootOrder, precedence[i][1]);
    }

    // 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 movie_shoot_scheduling.py instances\movie5.txt
Execution (Linux)
export PYTHONPATH=/opt/localsolver_9_5/bin/
python movie_shoot_scheduling.py instances/movie5.txt
########## movie_shoot_scheduling.py ##########

import traceback

import localsolver
import sys

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

class MssInstance:

    #
    # Read instance data
    #
    def __init__(self, filename):
        file_it = iter(read_integers(sys.argv[1]))
        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, 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][0])
                             < model.index(shoot_order, data.precedences[i][1]))

        # 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()

        print(shoot_order.value)

        # 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[0]
        if len(shoot_order) < self.data.nb_scenes:
            # Infeasible solution if some shoots 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 shoots 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



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[1]
    output_file = sys.argv[2] if len(sys.argv) >= 3 else None
    time_limit = int(sys.argv[3]) 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\localsolver95.lib
movie_shoot_scheduling instances\movie5.txt
Compilation / Execution (Linux)
g++ movie_shoot_scheduling.cpp -I/opt/localsolver_9_5/include -llocalsolver95 -lpthread -o movie_shoot_scheduling
./movie_shoot_scheduling instances/movie5.txt
/********** movie_Shoot_scheduling.cpp **********/

#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
#include "localsolver.h"
#include <limits>
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;

    /* Read instance data */
    void readInstance(const string& fileName) {
        ifstream infile;
        infile.exceptions(ifstream::failbit | ifstream::badbit);
        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:
    // Constructor
    MssInstance(const string& fileName) {
        readInstance(fileName);
        computeNbWorkedDays();
    }
};

/* External function */
class CostFunction : public LSExternalFunction<lsint> {
private:
    const MssInstance* instance;
    // To maintain thread-safety property, thread_local (since C++11) is used
    // here. Each thread must have have independant following variables.

    // Number of visits per location (group of successive shoots)
    static thread_local vector<int> nbLocationVisits;

    // Last day of work for each actor
    static thread_local vector<int> actorFirstDay;

    // Last day of work for each actor
    static thread_local vector<int> actorLastDay;

    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 shoots 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:
    // Constructor
    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 shoots 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:
    // Constructor
    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 shoots 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(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.exceptions(ofstream::failbit | ofstream::badbit);
        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;
    }
};

thread_local std::vector<int> CostFunction::nbLocationVisits;
thread_local std::vector<int> CostFunction::actorFirstDay;
thread_local std::vector<int> CostFunction::actorLastDay;

int main(int argc, char** argv) {
    if (argc < 2) {
        cerr << "Usage: movie_shoot_scheduling inputFile [outputFile] [timeLimit]" << endl;
        return 1;
    }
    const char* instanceFile = argv[1];
    const char* solFile = argc > 2 ? argv[2] : NULL;
    const char* strTimeLimit = argc > 3 ? argv[3] : "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
/********** MovieShootScheduling.cs **********/

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;

    // Constructor
    public MssInstance(string fileName)
    {
        ReadInstance(fileName);
        ComputeNbWorkedDays();
    }

    /* Read instance data */
    void ReadInstance(string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            string[] line;
            nbActors = int.Parse(input.ReadLine());
            nbScenes = int.Parse(input.ReadLine());
            nbLocations = int.Parse(input.ReadLine());
            nbPrecedences = int.Parse(input.ReadLine());
            input.ReadLine();
            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];

            line = input.ReadLine().Split();
            for (int j = 0; j < nbActors; ++j)
                actorCost[j] = int.Parse(line[j]);
            line = input.ReadLine().Split();
            for (int k = 0; k < nbLocations; ++k)
                locationCost[k] = int.Parse(line[k]);
            line = input.ReadLine().Split();
            for (int i = 0; i < nbScenes; ++i)
                sceneDuration[i] = int.Parse(line[i]);
            line = input.ReadLine().Split();
            for (int i = 0; i < nbScenes; ++i)
                sceneLocation[i] = int.Parse(line[i]);
            input.ReadLine();
            for (int j = 0; j < nbActors; ++j)
            {
                line = input.ReadLine().Split();
                for (int i = 0; i < nbScenes; ++i)
                    isActorInScene[j, i] = Convert.ToBoolean(int.Parse(line[i]));
            }
            input.ReadLine();
            for (int p = 0; p < nbPrecedences; ++p)
            {
                line = input.ReadLine().Split();
                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;

    // To maintain thread-safety property, ThreadStatic is used
    // here. Each thread must have have independant following variables.

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

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

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

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

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

        InitStaticVectors();
        ResetStaticVectors();

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

    private 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 shoots 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(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 = Convert.ToInt32(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()
    {
        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;

     // Constructor
    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 shoots 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 i-th 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[0];
        string outputFile = args.Length > 1 ? args[1] : null;
        string strTimeLimit = args.Length > 2 ? args[2] : "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_9_5/bin/localsolver.jar
java -cp /opt/localsolver_9_5/bin/localsolver.jar:. MovieShootScheduling instances/movie5.txt
/********** MovieShootScheduling.java **********/

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 {
            readInput(fileName);
            computeNbWorkedDays();
        }

        /* Read instance data */
        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][2];

                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;

        // To maintain thread-safety property, ThreadLocal is used here.
        // Each thread must have independant following variables.

        // Number of visits per location (group of successive shoots)
        private ThreadLocal<int[]> nbLocationVisits;

        // First day of work for each actor
        private ThreadLocal<int[]> actorFirstDay;

        // Last day of work for each actor
        private ThreadLocal<int[]> actorLastDay;

        /* 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);
            if (shootOrder.count() < instance.nbScenes) {
                // Infeasible solution if some shoots are missing
                return Integer.MAX_VALUE;
            }
            resetVectors();

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

        private int computeLocationCost(LSCollection shootOrder) {
            int previousLocation = -1;
            for (int i = 0; i < instance.nbScenes; i++) {
                int currentLocation = instance.sceneLocation[(int) shootOrder.get(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(LSCollection shootOrder) {
            // 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) shootOrder.get(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;

        // Constructor
        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 i-th 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][0]),
                        model.indexOf(shootOrder, instance.precedences[p][1])));

            // 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 i-th 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[0];
        String outputFile = args.length > 1 ? args[1] : null;
        String strTimeLimit = args.length > 2 ? args[2] : "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);
        }
    }
}