Constraint Knapsack

The constraint Knapsack ensures that some items are packed in a knapsack with certain weight and profit restrictions. So, the context is to manage a collection of items, each one being described by 2 attributes: its weight and its profit. We have to decide how many copies of each item must be selected (or simply, which items must be selected, in a single occurrence, if variables are 0/1) while respecting a numerical condition $({\odot }_w,k_w)$ on accumulated weights and a numerical condition $({\odot }_p,k_p)$ on accumulated profits.

The operator of the first condition is expected to be in $<,\le ,=$ whereas the operator of the second condition is expected to be in $>,\ge ,=$.

Ensuring a minimum benefit when filling a knapsack:

In PyCSP${}^3$, we must call the function Knapsack() that allows us to pass the variables either in sequence (individually) or under the form of a list. Two named parameters weights and profits are required. Then, we have to express twe two conditions (on weights and profits). On the one hand, the first condition, on weights, is given either by wlimit or wcondition: exactly one of these two parameters must be different from None. The value of wlimit is either an integer value or an integer variable (and the implicit operator is then $\le$). The value of wcondition can be built by calling a function among lt(), le(), eq(), … On the other hand, the second condition, on profits, is expressed on the object obtained when calling Knapsack(). Indeed, this object represents the accumulated profit and can then be restricted by a condition (typically, defined by a relational operator and a limit).

To see how this constraint works, we need first to import the library PyCSP${}^3$:

from pycsp3 import *

For our illustration, we assume that we have 10 items with the following weights and profits:

weights = [10, 2, 6, 11, 21, 4, 8, 3, 8, 10]
profits = [20, 4, 3, 9, 13, 2, 3, 4, 7, 8]
nItems = len(weights)

We also assume that we need to collect some of these items (in a knapsack) while considering that the capacity of the knapsack is 20 (w_limit) and the minimum satisfactory level is 30 (p_limit).

w_limit, p_limit = 20, 30

Next, we introduce an array $x$ of 10 variables, each variable having {0,1} as domain. We have $x[i]$ set to 1 iff the item i is packed (selected).

x = VarArray(size=nItems, dom={0, 1})

We can display (the structure of) the array as well as the domain of the first variable.

print("Array of variable x: ", x)
print("Domain of any variable: ", x[0].dom)

Array of variable x:  [x[0], x[1], x[2], x[3], x[4], x[5], x[6], x[7], x[8], x[9]]
Domain of any variable:  0 1

We simply post a single constraint Knapsack with the limits mentioned above.

satisfy(
     Knapsack(x, weights=weights, wlimit=w_limit, profits=profits) >= p_limit
);

By calling the function solve(), we can check that the problem (actually, the single constraint) is satisfiable (SAT). We can also print the values assigned to the variables in the found solution; we can call the function values() that collects the values assigned (in the last found solution) to a specified list of variables.

if solve() is SAT:
    print("Values of x: ", values(x))

Values of x:  [1, 1, 0, 0, 0, 1, 0, 1, 0, 0]

On this simple constraint, one can verify that the number of solutions (supports) is 2.

if solve(sols=ALL) is SAT:
     for i in range(n_solutions()):
        print(f"Solution {i+1}: {values(x, sol=i)} of profit {sum(value(x[j], sol=i)*profits[j] for j in range(nItems))}")

Solution 1: [1, 1, 0, 0, 0, 1, 0, 1, 0, 0] of profit 30
Solution 2: [1, 1, 0, 0, 0, 0, 0, 0, 1, 0] of profit 31

Let us display the internal representation of the posted constraint:

print(posted())

knapsack(list:x[], weights:[10, 2, 6, 11, 21, 4, 8, 3, 8, 10], limit:(le,20), profits:[20, 4, 3, 9, 13, 2, 3, 4, 7, 8], condition:(ge,30))

Now, let us discard it:

unpost()

Let us check that there are no more constraints:

print(posted())

[]

Let us post the same constraint, this time by using the other parameter wcondition:

satisfy(
     Knapsack(x, weights=weights, wcondition=le(w_limit), profits=profits) >= p_limit
);

Let us check that this is the same constraint:

print(posted())

knapsack(list:[x[0], x[1], x[2], x[3], x[4], x[5], x[6], x[7], x[8], x[9]], weights:[10, 2, 6, 11, 21, 4, 8, 3, 8, 10], limit:(le,20), profits:[20, 4, 3, 9, 13, 2, 3, 4, 7, 8], condition:(ge,30))

Since XCSP${}^3$ Specifications 3.1, Knapsack belongs to XCSP${}^3$-core (notably because solvers not equipped with a specific propagator can handle that constraint easily by posting two constraints Sum).

Related Models