Question about expected behavior for knapsack constraint

[paulk-asert]

Hi, I was doing a little example of a knapsack problem:

int[] values = [1, 5, 10, 15, 17] // energies
int[] weights = [1, 2, 3, 5, 6]

When using the knapsack constraint, it seems I still have to set a MAXIMIZE objective? Or am I doing something wrong?
My code is here:

https://github.com/paulk-asert/groovy-knapsack/blob/main/src/main/groovy/choco/Builtin.groovy

When I run I get:

[count0 = 0, count1 = 2, count2 = 2, count3 = 0, count4 = 0]
Total weight taken = 10
Total value for capacity 10 (unbounded) = 30

If I leave out the setObjective(MAXIMIZE, total) I get:

[count0 = 6, count1 = 2, count2 = 0, count3 = 0, count4 = 0]
Total weight taken = 10
Total value for capacity 10 (unbounded) = 16

I would have thought that objective would be part of the knapsack constraint?

Also, I have a version coding the constraints "long-hand" with some explicit search hints:

https://github.com/paulk-asert/groovy-knapsack/blob/main/src/main/groovy/choco/Constraints.groovy

Running this gives the expected maximum value:

[count0 = 1, count1 = 0, count2 = 3, count3 = 0, count4 = 0]
Total value for capacity 10 (unbounded) = 31

Do I need extra search hints for the knapsack constraint too?

[cprudhom]

I would have thought that objective would be part of the knapsack constraint?

Actually, the objective is considered within the constraint, for filtering, but you still have to define it as a goal.

Do I need extra search hints for the knapsack constraint too?

I don't know Groovy, but it seems that you are looking the first solution only.

In java your code would look like:

int[] energies = {1, 5, 10, 15, 17}; // energies
int[] weights = {1, 2, 3, 5, 6};
int nos = energies.length;
Model model = new Model("Knapsack");
// occurrence of each item
IntVar[] counts = new IntVar[nos];
for (int i = 0; i < nos; i++) {
    counts[i] = model.intVar("counts_" + (i + 1), 0, 10);
}
// objective variable
IntVar totalValue = model.intVar("power", 0, 100000);
IntVar scalar = model.intVar("weight", 0, 10);
model.knapsack(counts, scalar, totalValue, weights, energies).post();
model.setObjective(MAXIMIZE, totalValue);
if(model.getSolver().solve()){
    System.out.printf("Power : %s, ", totalValue.getValue());
    System.out.printf("Objects : %s\n", Arrays.toString(counts));
}

Running this looks (and stops) for the first solution.
If you turn if into while, the solver will list (improving) solutions until you reach the optimal solution and eventually prove its optimality.
You can read the following page for more details : Lauching the resolution process.

[paulk-asert]

Thanks, that indeed fixed my problem. It is a while since I last used Choco. It's a great library - kudos to the team.