Intro

In the previous knapsack post we showed a basic branch and bound approach to solving the knapsack problem. This is a notebook of experiments on different ways to improve the performance .

Functions

See the previous knapsack post for what these are and how they fit.

branch←{⍪,((,/,∘0),(,/,∘1))⍤1⊢⍵}

]dinput
weight←{
    c mw is←⍺           ⍝ split the right argument into components count, max weight, and items
    vs ws←↓⍉↑is         ⍝ extract a list of values and a list of weights from the item lis
    psolution←c↑⍵       ⍝ pad the partial solution with 0s to the lenght of the item list
    +/ws∧psolution      ⍝ use the partial solution as a mask to select the weights of the items we take and sum them
}

]dinput
value←{
    c mw is←⍺
    mw≤⍺ weight ⍵ :0 ⍝ if the weight is more than the capacity the value is 0
    vs ws←↓⍉↑is
    psolution←c↑⍵
    +/vs∧psolution
}

]dinput
greedy←{
 c mw is←⍺
 cw←⍺ weight ⍵
 c ≤ ⍴⍵: ⍺ value ⍵ ⍝ stop if we have looked at all items
 mw=cw: ⍺ value ⍵  ⍝ stop if knapsack is full
 mw<cw: 0          ⍝ stop if knapsack is overfull
 v w←⊃is↓⍨⍴⍵       ⍝ drop items that have already been considered
 ⍺∇⍵,w≤mw-cw       ⍝ recurse with an additional item considered
}

]dinput
optimistic←{
     c mw is←⍺

     vs ws←↓⍉↑is

     cv ← ⍺ value ⍵
     cw ← ⍺ weight ⍵

     vs ws←↓⍉↑is↓⍨⍴⍵                     ⍝ drop the items already decided
     cw>mw:0                             ⍝ if the weight already exceeds max capacity return 0
     d←(⍴⍵)↓÷⌿⍤1⊢↑is                     ⍝ density
     cv++/d×ws⌊0⌈¯1↓(mw-cw),(mw-cw)-+\ws ⍝ current value plus optimistic guess for remainder

 }

]dinput
bound←{
     best ks←⍺
     ⍵⌿⍨best≤ks∘optimistic∘⊃⍤1⊢⍵    ⍝ filter branches where the best solution is less than the optimistic solution 
 }

]dinput
read_ks←{
     temp←↓⍎⍤1⊢↑⊃⎕NGET ⍵ 1
     count max_weight←⊃temp
     items←1↓temp
     items←items⌷⍨⊂⍒÷⌿⍤1⊢↑items
     count max_weight items
 }

]dinput
solver1←{
     c mw is←⍵
     g←⍵ greedy ⍬
     s←g ⍵∘bound∘branch⍣c⊢⍬
     ⊃(,s)⌷⍨⊂⍒⍵∘value∘⊃⍤1⊢s
}

Baseline

First lets make it easy to run experiments

'time' ⎕cy 'dfns'

]dinput
experiment←{
    knapsack←read_ks ⍵
    s←⍺⍺ time knapsack
    (knapsack value s) (knapsack weight s)
}

solver1 experiment 'ks_1000_0'

┌→───────┐ │25:06.61│ └────────┘ ┌→───────────┐ │109899 99999│ └~───────────┘

25 minutes for these particular 1000 items

Experiments

Bound

One of the issues is the how we prune branches. If we have too low of a value it doesn’t prune very many branches. The current solver only uses the greedy value and we never update this.

The way things currently work is we branch, we calculate the optimistic values and we compare. What if we branch, calculate the optimistic values, take the 5 highest value branches and use those as the starting point for our greedy algorithm. We take the highest value between those and use that to prune our branches.

]dinput
solver2_←{
    ks←⍺
    c mw is←ks
    branches←{⍵⌷⍨∘⊂∘⍒ ks∘optimistic∘⊃⍤1⊢⍵} branch ⍵
    best←⌈/ks∘greedy∘⊃⍤1⊢5↑branches
    ret←branches⌿⍨best≤ks∘optimistic∘⊃⍤1⊢branches
    ret
}

]dinput
solver2←{
    c mw is←⍵
    ss←⍵∘solver2_⍣(c-1)⊢ branch⍣2⊢⍬
    ⊃ss
}

solver2 ks19

┌→──────────┐ │12248 30996│ └~──────────┘

solver2 experiment 'ks_1000_0'

┌→────┐ │31.96│ └─────┘ ┌→───────────┐ │109899 99999│ └~───────────┘

Huge success. We went from 25 minutes to 32 seconds.