CODEWITHSUNDEEP
javaconstraintsconstraint-programming
Omarou
Omarou

Reputation: 47

Safe packing - Choco-solver

Problem:

You need to pack several items into your shopping bag without squashing anything. The items are to be placed one on top of the other. Each item has a weight and a strength, defined as the maximum weight that can be placed above that item without it being squashed. A packing order is safe if no item in the bag is squashed, that is, if, for each item, that item’s strength is at least the combined weight of what’s placed above that item. For example, here are three items and a packing order:

enter image description here

This packing is not safe. The bread is squashed because the weight above it, 5, is greater than its strength, 4. Swapping the apples and the bread, however, gives a safe packing.

Goal:

I need to find all the solutions to this problem with choco solver then test if this solution is enumerated:

N=3, WS = { (5,6), (4,4), (10,10) }

What I tried:

First I wrote my CSP model

enter image description here

Then I wrote my choco code like that

public static void main(String[] args) {
    int[][] InitialList = {{5,6}, {4,4}, {10,10}};
    int N = InitialList.length;

    Model model = new Model("SafePacking");

    // Create IntVars of weights and strengths
    IntVar[] weights = new IntVar[N], strengths = new IntVar[N];
    for (int i = 0; i < N; i++) {
        weights[i] = model.intVar("Weight"+i, InitialList[i][0]);
        strengths[i] = model.intVar("Strength"+i, InitialList[i][1]);
    }

    // Create IntVar of positions
    IntVar[] positions = model.intVarArray("P",N, 0, N-1);
    model.allDifferent(positions).post();

    for(int i = 0; i < N; i++) {
        int sum = 0;
        for(int j = 0; j < N; j++)
            if (positions[j].getValue() < positions[i].getValue())
                sum += weights[j].getValue();
        model.arithm(model.intVar(sum), "<=", strengths[i]).post();
    }

    Solution solution = model.getSolver().findSolution();
    System.out.println(solution);

}

But I've got this result :

Solution: P[0]=0, P[1]=1, P[2]=2

Which is a wrong solution. Did I miss something ?

Upvotes: 0

Views: 143

Answers (1)

Zayenz
Zayenz

Reputation: 1964

The computation of sum seems to assume that the variables have a defined value, which they do not have. Calling getValue() on an uninstantiated IntVar will give the lower bound for a variable in Choco.

To make your model work, you need to build up sum as an IntVar instead.

Upvotes: 5

Related Questions