ToySolver.Combinatorial.SubsetSum

References

• D. Pisinger, "An exact algorithm for large multiple knapsack problems," European Journal of Operational Research, vol. 114, no. 3, pp. 528-541, May 1999. DOI:10.1016/s0377-2217(98)00120-9 http://www.sciencedirect.com/science/article/pii/S0377221798001209 http://www.diku.dk/~pisinger/95-6.ps

Documentation

type Weight = Integer

subsetSum

Arguments

:: Vector v Weight

=> v Weight

weights [w1, w2 .. wn]

-> Weight

l

-> Maybe (Vector Bool)

the assignment [x1, x2 .. xn], identifying 0 (resp. 1) with False (resp. True).

Solve Σ_{i=1}^n wi x = c and xi ∈ {0,1}.

Note that this is different from usual definition of the subset sum problem, as this definition allows all xi to be zero.

Note: 0 (resp. 1) is identified with False (resp. True) in the assignment.

maxSubsetSum

Arguments

:: Vector v Weight

=> v Weight

weights [w1, w2 .. wn]

-> Weight

capacity c

-> Maybe (Weight, Vector Bool)

• the objective value Σ_{i=1}^n wi xi, and
• the assignment [x1, x2 .. xn], identifying 0 (resp. 1) with False (resp. True).

Maximize Σ_{i=1}^n wi xi subject to Σ_{i=1}^n wi xi ≤ c and xi ∈ {0,1}.

Note: 0 (resp. 1) is identified with False (resp. True) in the assignment.

minSubsetSum

Arguments

:: Vector v Weight

=> v Weight

weights [w1, w2 .. wn]

-> Weight

l

-> Maybe (Weight, Vector Bool)

• the objective value Σ_{i=1}^n wi xi, and
• the assignment [x1, x2 .. xn], identifying 0 (resp. 1) with False (resp. True).

Minimize Σ_{i=1}^n wi xi subject to Σ_{i=1}^n wi x≥ l and xi ∈ {0,1}.

Note: 0 (resp. 1) is identified with False (resp. True) in the assignment.