Stochastic Packing¶

import java.util.Random;

import localsolver.*;

public class StochasticPacking {
    // Number of items
    private int nbItems;

    // Number of bins
    private int nbBins;

    // Number of scenarios
    private int nbScenarios;

    // For each scenario, the weight of each item
    private int[][] scenarioItemWeights;

    // LocalSolver
    private final LocalSolver localsolver;

    // Decision variable for the assignment of items
    private LSExpression[] bins;

    // For each scenario, the corresponding max weight
    private LSExpression[] scenarioMaxWeight;

    // Objective = minimize the 9th decile of all possible max weights
    private LSExpression stochasticMaxWeight;

    private void generateScenarios(int rngSeed) {
        Random rng = new Random(rngSeed);

        // Pick random parameters for each item distribution
        int[] itemsMin = new int[nbItems];
        int[] itemsMax = new int[nbItems];
        for (int i = 0; i < nbItems; ++i) {
            itemsMin[i] = 10 + rng.nextInt(91);
            itemsMax[i] = itemsMin[i] + rng.nextInt(51);
        }

        // Sample the distributions to generate the scenarios
        scenarioItemWeights = new int[nbScenarios][nbItems];
        for (int i = 0; i < nbScenarios; ++i) {
            for (int j = 0; j < nbItems; ++j) {
                scenarioItemWeights[i][j] = itemsMin[j] + rng.nextInt(itemsMax[i] - itemsMin[i] + 1);
            }
        }
    }

    private StochasticPacking(LocalSolver localsolver, int nbItems, int nbBins, int nbScenarios, int rngSeed) {
        this.localsolver = localsolver;
        this.nbItems = nbItems;
        this.nbBins = nbBins;
        this.nbScenarios = nbScenarios;
        generateScenarios(rngSeed);
    }

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

        bins = new LSExpression[nbBins];
        scenarioMaxWeight = new LSExpression[nbScenarios];

        // Set decisions: bins[k] represents the items in bin k
        for (int k = 0; k < nbBins; ++k) {
            bins[k] = model.setVar(nbItems);
        }

        // Each item must be in one bin and one bin only
        model.constraint(model.partition(bins));

        // Compute max weight for each scenario
        for (int m = 0; m < nbScenarios; ++m) {
            LSExpression scenario = model.array(scenarioItemWeights[m]);
            LSExpression weightLambda = model.lambdaFunction(i -> model.at(scenario, i));
            LSExpression[] binWeights = new LSExpression[nbBins];

            for (int k = 0; k < nbBins; ++k) {
                binWeights[k] = model.sum(bins[k], weightLambda);
            }
            scenarioMaxWeight[m] = model.max(binWeights);
        }

        // Compute the 9th decile of scenario makespans
        LSExpression scenarioMaxWeightArray = model.array(scenarioMaxWeight);
        LSExpression sortedScenarioMaxWeight = model.sort(scenarioMaxWeightArray);
        stochasticMaxWeight = model.at(sortedScenarioMaxWeight, (int) Math.ceil(0.9 * (nbScenarios - 1)));

        model.minimize(stochasticMaxWeight);
        model.close();

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

        localsolver.solve();
    }

    /* Write the solution */
    private void writeSolution() {
        System.out.println();
        System.out.println("Scenario item weights:");
        for (int i = 0; i < nbScenarios; ++i) {
            System.out.print("" + i + ": [");
            for (int j = 0; j < nbItems; ++j) {
                System.out.print("" + scenarioItemWeights[i][j] + (j == nbItems - 1 ? "" : ", "));
            }
            System.out.println("]");
        }

        System.out.println();
        System.out.println("Bins:");

        for (int m = 0; m < nbBins; ++m) {
            System.out.print("" + m + ": { ");
            LSCollection items = bins[m].getCollectionValue();
            for (int i = 0; i < items.count(); ++i) {
                System.out.print("" + items.get(i) + (i == items.count() - 1 ? " " : ", "));
            }
            System.out.println("}");
        }
    }

    public static void main(String[] args) {
        try (LocalSolver localsolver = new LocalSolver()) {
            int nbItems = 10;
            int nbBins = 2;
            int nbScenarios = 3;
            int rngSeed = 42;
            int timeLimit = 2;

            StochasticPacking model = new StochasticPacking(localsolver, nbItems, nbBins, nbScenarios,
                rngSeed);

            model.solve(timeLimit);
            model.writeSolution();
        } catch (Exception ex) {
            System.err.println(ex);
            ex.printStackTrace();
            System.exit(1);
        }
    }
};