Rima: The Knapsack Problem

[ Contents ]

This is a Rima version of the "burglar bill" XPress knapsack example. A knapsack problem involves picking items to fill a knapsack of limited capacity with items of maximum value. We have a list of items, each with a weight and capacity, and wish to choose which we'll take.

We start by requiring the Rima module:

rima = require("rima")

Then we define some variables, or references with rima.R. Note that at this stage we don't have to tell Rima anything about the types of our variables, or whether they're parameters or variables we wish to solve for. We define references to our list of items, a reference to use for a single item and the total capacity of the knapsack:

i, items = rima.R"i, items"
capacity = rima.R"capacity"

Next, we define our two equations, one for the value of the items we're putting in the knapsack, and one for the weight of the items. Note that we're using syntax like item.take, item.value and item.size - Rima understands data structures like a dynamic language should. Also, we haven't defined these fields or structures at all, when Rima has the data, it'll check it works as expected - duck typing for a modelling language!

value = rima.sum{i=items}(i.take * i.value)
size = rima.sum{i=items}(i.take * i.size)

We create a new formulation, set its objective:

knapsack = rima.mp.new()
knapsack.sense = "maximise"
knapsack.objective = value

Rima accepts both "maximise" and "maximize" (as well as "MaXiMiZe").

We use rima.mp.C to construct a constraint, and add it to the scope like any other value::

knapsack.capacity_limit = rima.mp.C(size, "<=", capacity)

Finally, we define item.take as a binary variable:

knapsack.items[{i=items}].take = rima.binary()

And we're done. knapsack is a complete definition of a knapsack problem. You can derive from it, compose a new model with it, make a Lua module out of it and we can even write it out in a readable format:

print(knapsack)
--> Maximise:
-->   sum{i in items}(i.take*i.value)
--> Subject to:
-->   capacity_limit: sum{i in items}(i.size*i.take) <= capacity
-->   items[i].take binary for all i in items

So far, we've seen no data, other than the one bit we wanted - defining as items[item].picked as a binary variable. Of course, we can't solve anything without data.

Data is easy to add: it's just a regular Lua table:

burglar_bill =
{
  capacity = 102,
  items =
  {
    camera   = { value =  15, size =  2 },
    necklace = { value = 100, size = 20 },
    vase     = { value =  15, size = 20 },
    picture  = { value =  15, size = 30 },
    tv       = { value =  15, size = 40 },
    video    = { value =  15, size = 30 },
    chest    = { value =  15, size = 60 },
    brick    = { value =   1, size = 10 },
  }
}

To solve the problem use the solve method to combine the model and data:

primal, dual = rima.mp.solve(knapsack, burglar_bill)

We can check the objective:

print(primal.objective)                           --> 160

And see if it was worth taking the brick or necklace in the knapsack:

print(primal.items.brick.take)                    --> 0
print(primal.items.necklace.take)                 --> 1

[ Contents ]