Movie Shoot Scheduling Problem

import hexaly.optimizer
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(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, time_limit):
    data = MssInstance(instance_file)

    with hexaly.optimizer.HexalyOptimizer() as optimizer:
        #
        # Declare the optimization model
        #
        model = optimizer.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 optimizer
        optimizer.param.time_limit = time_limit if len(sys.argv) >= 4 else 20
        optimizer.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[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


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)

#include "optimizer/hexalyoptimizer.h"
#include <fstream>
#include <iostream>
#include <limits>
#include <string.h>
#include <vector>
using namespace hexaly;
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:
    MssInstance(const string& fileName) {
        readInstance(fileName);
        computeNbWorkedDays();
    }
};

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

    // Number of visits per location (group of successive scenes)
    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(HxCollection 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(HxCollection 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) {}

    hxint call(const HxExternalArgumentValues& argumentValues) {
        HxCollection 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:
    // Hexaly Optimizer
    HexalyOptimizer optimizer;

    // Instance data
    const MssInstance* instance;

    // Decision variable
    HxExpression shootOrder;

    // Objective
    HxExpression callCostFunc;

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

    void solve(int limit) {
        // Declare the optimization model
        HxModel model = optimizer.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][0]) <
                             model.indexOf(shootOrder, instance->precedence[p][1]));

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

        model.close();

        // Parameterize the optimizer
        optimizer.getParam().setTimeLimit(limit);

        optimizer.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;
        HxCollection 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;
    }
}

using System;
using System.IO;
using Hexaly.Optimizer;

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)
    {
        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 independant following variables.

    // Number of visits per location (group of successive scenes)
    [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;

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

    public long Call(HxExternalArgumentValues argumentValues)
    {
        HxCollection 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
{
    // Hexaly Optimizer
    HexalyOptimizer optimizer;

    // Instance data
    MssInstance instance;

    // Decision variable
    HxExpression shootOrder;

    // Objective
    HxExpression callCostFunc;

    public MovieShootScheduling(MssInstance instance)
    {
        this.optimizer = new HexalyOptimizer();
        this.instance = instance;
    }

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

    void Solve(int limit)
    {
        // Declare the optimization model
        HxModel model = optimizer.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);
        HxIntExternalFunction func = new HxIntExternalFunction(costObject.Call);
        HxExpression costFunc = model.CreateIntExternalFunction(func);
        costFunc.GetExternalContext().SetIntLowerBound(0);
        callCostFunc = model.Call(costFunc, shootOrder);
        model.Minimize(callCostFunc);

        model.Close();

        // Parameterize the optimizer
        optimizer.GetParam().SetTimeLimit(limit);

        optimizer.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());
            HxCollection 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);
        }
    }
}

import java.util.Scanner;
import java.io.*;
import com.hexaly.optimizer.*;

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 HxIntExternalFunction {

        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 scenes)
        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(HxExternalArgumentValues argumentValues) {
            HxCollection 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 {

        // Hexaly Optimizer
        private final HexalyOptimizer optimizer;

        // Instance data
        private final MssInstance instance;

        // Decision variable
        private HxExpression shootOrder;

        // Objective
        private HxExpression callCostFunc;

        private MSSProblem(HexalyOptimizer optimizer, MssInstance instance) {
            this.optimizer = optimizer;
            this.instance = instance;
        }

        private void solve(int limit) {
            // Declare the optimization model
            HxModel model = optimizer.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][0]),
                    model.indexOf(shootOrder, instance.precedences[p][1])));

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

            model.close();

            // Parameterize the optimizer
            optimizer.getParam().setTimeLimit(limit);

            optimizer.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());
                HxCollection 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 (HexalyOptimizer optimizer = new HexalyOptimizer()) {
            MssInstance instance = new MssInstance(instanceFile);
            MSSProblem model = new MSSProblem(optimizer, instance);
            model.solve(Integer.parseInt(strTimeLimit));
            if (outputFile != null) {
                model.writeSolution(outputFile);
            }
        } catch (Exception ex) {
            System.err.println(ex);
            ex.printStackTrace();
            System.exit(1);
        }
    }
}