Tutorials

Solving knapsack problems

Learn to model a knapsack problem with the Nextmv SDK

The Nextmv Software Development Kit (SDK) lets you automate any operational decision in a way that looks and feels like writing other code. It provides the guardrails to turn your data into automated decisions and test and deploy them into production environments.

Introduction

This tutorial will walk you through our knapsack template. It assumes you already completed the steps described in the 5-minute getting started experience.

To test that the Nextmv CLI is correctly configured, run the following command on your terminal. It will ensure you have the necessary files to work with the Nextmv Platform.

$ nextmv install
checking go and sdk version support...
downloading sdk files...
successfully installed sdk files
Copy

Now that you are all set up, you can officially start the tutorial. To get the template, simply run the following command.

$ nextmv init -t knapsack
Successfully generated the knapsack template in <localPath>/knapsack
Copy

You can check that all files are available in the newly created knapsack/folder. Running the following command you should see this file structure.

$ cd knapsack
knapsack$ ls
README.md               go.sum                  knapsack.code-workspace main.go
go.mod                  input.json              license
Copy
  • license contains the Apache License 2.0 under which we distribute this template.
  • README.md gives a short introduction to the knapsack problem and shows you how to run the template.
  • go.mod and go.sum define a Go module and are used to manage dependencies, including the Nextmv SDK.
  • The knapsack.code-workspace file should be used to open the template in Visual Studio Code. It is pre-configured for you so that you can run and debug the template without any further steps.
  • input.json describes the input data for a specific knapsack problem that is solved by the template.
  • main.go contains the actual code of knapsack app.

Run the template with the given input file using Nextmv CLI.

knapsack$ nextmv run local main.go -- -hop.runner.input.path input.json \
    -hop.solver.limits.duration 5s \
    -hop.solver.diagram.expansion.limit 1    
--------------------------------------------------------------------------------
This software is provided by Nextmv.

© 2019-2022 nextmv.io inc. All rights reserved.

    (\/)     (\/)     (\/)     (\/)     (\/)     (\/)     (\/)     (\/)     (\/)
    (^^)     (^^)     (^^)     (^^)     (^^)     (^^)     (^^)     (^^)     (^^)
   o( O)    o( O)    o( O)    o( O)    o( O)    o( O)    o( O)    o( O)    o( O)
--------------------------------------------------------------------------------
{"version":{"sdk":"v0.19.0"},"options":{"diagram":{"expansion":{"limit":1},
"width":10},"limits":{"duration":"5s"},"search":{"buffer":100},"sense":
"maximize"},"store":{"items":[{"id":"keys","value":92,"weight":1},{"id":"rx",
"value":81,"weight":1},{"id":"water","value":40,"weight":2},{"id":"book",
"value":63,"weight":10},{"id":"phone","value":6,"weight":1},{"id":"cat",
"value":100,"weight":20},{"id":"coat","value":44,"weight":9},{"id":"nuts",
"value":18,"weight":4}],"value":444,"weight":48},"statistics":{"bounds":
{"lower":444,"upper":452},"search":{"generated":179,"filtered":5,"expanded":174,
"reduced":0,"restricted":72,"deferred":102,"explored":63,"solutions":9},"time":
{"elapsed":"1.642333ms","elapsed_seconds":0.001642333,
"start":"2022-09-14T15:45:21.217268+02:00"},"value":444}}
Copy

If you see something like shown above: Great job, you successfully ran the template. Now lets look into the knapsack app step by step which is defined in the main.go.

Dissecting the app

The first part of the main.go defines a package name, imports packages that are needed by the model and creates a main function - the starting point for the app. We create a runner using the Run function from the Nextmv run package. This function executes a solver, defined below.

package main

import (
	"math"
	"sort"

	"github.com/nextmv-io/sdk/run"
	"github.com/nextmv-io/sdk/store"
)

func main() {
	run.Run(solver)
}
Copy

The Input

But before we look into the solver function, we will examine the two structs Knapsack and Item.

// A Knapsack holds the most valuable set of items possible while not exceeding
// its carrying capacity.
type Knapsack struct {
	Items    []Item `json:"items"`    // potential items for packing
	Capacity int    `json:"capacity"` // weight the knapsack can hold
}

// Item represents an item than can be put into the knapsack.
type Item struct {
	ID     string `json:"id"`
	Value  int    `json:"value"`
	Weight int    `json:"weight"`
}
Copy

The Knapsack struct has two fields. Capacity and Items, where Capacity describes the overall capacity of the knapsack in weight and Items holds a slice of potential items to pack. Those items are represented as a struct and have an ID (a unique name that helps you identify the item later), a Value (the value of adding the item), and it's Weight (the cost to the Knapsack Capacity for adding thee item).

Note that the json:"XXX" after the fields make use of a Go feature to automatically map the data from the input.json to those entities and fields.

The Solver

The solver function is where the model is defined. The function's signature adheres to the run.Run function we saw earlier already.

func solver(input Knapsack, opts store.Options) (store.Solver, error) {
Copy

When you first ran the template you passed in the parameter -hop.runner.input.path followed by the path to an input file. This file is automatically parsed and converted to our Knapsack struct. Other option arguments are also interpreted automatically passed to the solver as an Options struct.

The app tries to pack items by efficiency or the ratio of the value and weight of each Item. We use the Go package sort to make sure the items are in the correct order. This ensures we make decisions about the most efficient items first (the most value per weight).

// Hence, we sort them here.
sort.SliceStable(input.Items, func(i, j int) bool {
	value := func(x Item) float64 {
		return float64(x.Value) / float64(x.Weight)
	}
	return value(input.Items[i]) > value(input.Items[j])
})
Copy

We then create a store called knapsack which holds all the decision variables we need to track. In this case our store knapsack will have the integer variables value, weight and itemIdx. We also add a slice trace to it to track the decisions we have made.

  • value: represents the total knapsack's value of the current store. At the beginning, when no decision was made yet this value is 0.
  • weight: represents the knapsack's total weight of the current store. At the beginning when no decision was made yet this value is 0.
  • itemIdx: indicates up to which item (by index) we made a decision. Since at the beginning no decision was made yet the value is set to -1.
  • trace: tracks wether or not we decided to put an item into the knapsack or not up until now.

// We create a new store that stores everything we need to construct valid
// knapsack solutions.
knapsack := store.New()

// We store the value of the knapsack (i.e. the sum of all item values).
value := store.NewVar(knapsack, 0)
// We store the weight of the knapsack (i.e. the sum of all item weights).
weight := store.NewVar(knapsack, 0)
// itemIdx points to the most recent item we either put in our knapsack
// or not.
itemIdx := store.NewVar(knapsack, -1)
// `trace`` stores our decisions along the way recording for each item
// until `itemIdx` if it is part of the knapsack or not.
trace := store.NewSlice[bool](knapsack)
Copy

Note that to create an integer variable for our store, we use store.NewVar and pass it a store that we want our new variable to be part of and a starting value. So in the following case we pass our knapsack and 0:

// We store the value of the knapsack (i.e. the sum of all item values).
value := store.NewVar(knapsack, 0)
Copy

Similarly, we use store.NewSlice to create a new slice of bool values for our store:

trace := store.NewSlice[bool](knapsack)
Copy

Now we define functions that operate on our store knapsack to find the best plan. First, we will explain briefly what they are doing before we look at them in detail.

  • Generate: The Generate function is used to find new solutions by creating new stores. Undoubtedly, this is a very important part of the app because it defines how the search space is traversed.
  • Validate: The Validate function checks if a solution fulfills certain criteria and thus, can be brought into operation.
  • Value: The Value function calculates and returns the store's value.
  • Bound: The Bound function sets a lower and upper bound to improve performance when searching for new solutions.
  • Format: The Format function changes the solution's output format, e.g. to be human-readable or better suited for post-processing the solution.

The Generate function

The Generate function is used to generate the search tree and traverse the search space. In this template, we use the Lazy function to achieve this. But before we call the Lazy function we define two helper variables:

  • From the current store, we first get the index of the item we now need to make a decision about next. The first time we enter this function the next value will be 0.
  • We also define a helper variable to later make sure we branch on the options we have: do pack the current item or do not pack the current item.
knapsack = knapsack.Generate(func(s store.Store) store.Generator {
	next := itemIdx.Get(s) + 1
	// i is a counter that ensures we only generate two new stores: one
	// with the item and one without.
	i := 0
Copy

The Lazy function returns a new Generator of stores. It does this lazily, meaning on demand, and does this until there are no new stores to be created based on the current store.

To achieve this, the Lazy function takes two functions as arguments. The first function controls if we want to generate new child stores given the current store.

// item in the knapsack (weight.Get(s) <= input.Capacity).
func() bool {
	return i <= 2 && next < len(input.Items) &&
		weight.Get(s) <= input.Capacity
},
Copy

In this case the condition to continue branching when all of the following is true:

  • we do not have any more items to make a decision about.
  • the current store's capacity is not exceeded.
  • the value for i is less than or equal to 2, ensuring that we branch twice on each store: pack the item or do not pack the item.

The second function takes a store and generates new child stores. At each child store, the Generate function will be called to create new stores and so on.

Let's see how we create a child store. First we create a slice of changes to apply to the store.

func() store.Store {
Copy

We then increase the value of i by 1. Given that the first function stops the generation process once i > 2, we know that after this step it is either 1 or 2.

Next, we can turn this value into a bool, where 1 means true and 2 means false.

On the first call of the function on the current store takeItem is true. So, we decide to put the item with index next into our knapsack and make the appropriate changes to the store, like setting the new weight and value, we add the item to the slice of traced items trace and set the itemIdx to next.

takeItem := i == 1
if takeItem {
	newWeight := weight.Get(s) + input.Items[next].Weight
	changes = append(changes,
		weight.Set(newWeight),
		value.Set(value.Get(s)+input.Items[next].Value),
		trace.Append(takeItem),
		itemIdx.Set(next),
	)
} else {
Copy

Child stores are generated by applying a set of changes to the parent store. Thus we append every change we need to make to the store to the slice of changes we instantiated before. To generate these changes we need to use the special functions Set and Append, respectively.

We do not enter the else block and return a new store by applying the changes.

return s.Apply(changes...)
Copy

The second and last time we enter this function on the same store as before, i is 2 and takeItem will evaluate to false. Thus, this time we decide to not put the item into our knapsack and the else block is entered.

} else {
	changes = append(changes,
		trace.Append(takeItem),
		itemIdx.Set(next),
	)
}
Copy

Since we do not put the item into the knapsack, we do not change weight or value but only trace and itemIdx. As before we return a new store by applying the changes:

return s.Apply(changes...)
Copy

Note that i has been changed from the first to the second call of the function on the store, while next has not. That way the store has exactly two children, one in which we add an item at index next and one where we don't.

On each of the returned stores the Generate function is called again and thus, branches each store until there are no new stores returned.

The Validate function

The Validate function checks whether a store is an operationally valid solution or not. For our knapsack this means that we must not exceed its capacity.

}).Validate(
	// The store is operationally valid if the capacity is not exceeded.
	func(s store.Store) bool {
		return weight.Get(s) <= input.Capacity
	}).Value(
Copy

The Value function

Now we calculate the store's value to evaluate whether one store is better than another. Since we want to maximize the knapsack's value, we just return its current value.

	}).Value(
	// Define the value of a store for optimization, the value is the sum
	// of the values of the individual items in the knapsack.
	value.Get,
).Bound(
Copy

The Bound function

With the Bound function we want to estimate the lower and upper bound for the knapsack based on the current store, if we continued the search from here. So, we are looking to estimate what the best possible value for the store (or our knapsack) can be right now.

For the lower bound this means we can at least achieve the current store's value. To estimate the upper bound we try to add all the remaining items until the knapsacks capacity is reached. If an item does not fully fit, we add it partially.

We first define variables that help us calculating the upper bound:

func(s store.Store) store.Bounds {
	upperBound := float64(value.Get(s))
	currentWeight := float64(weight.Get(s))
Copy

Here we set the starting point of our upper bound to our current store's value, which is also the lower bound, then we get the current weight and the index of the last item we added to our knapsack.

Next we loop over the remaining items that we have not made a decision about. Each time we calculate the space (in weight) the knapsack has left and get the weight of the item we are about to add and its value:

lastItemIdx := itemIdx.Get(s)
for i := lastItemIdx + 1; i < len(input.Items); i++ {
	spaceLeft := float64(input.Capacity) - currentWeight
	weightNeeded := float64(input.Items[i].Weight)
	val := float64(input.Items[i].Value)
Copy

If the item we are looking at still fits fully into our knapsack, we increase the upper bound by the item's value and increase the knapsack's current weight accordingly.

val := float64(input.Items[i].Value)
if weightNeeded <= spaceLeft {
	upperBound += val
	currentWeight += weightNeeded
} else {
Copy

And if the item does not fully fit, we calculate how much of the item still fits and add the corresponding value to upper bound. Since we cannot fit in any more items we break out of the loop.

} else {
	// in this case we just take the part of the item
	// after that our knapsack is full
	fraction := spaceLeft / weightNeeded
	upperBound += fraction * val
	break
}
Copy

Finally, we return our lower and upper bound:


return store.Bounds{
	Lower: value.Get(s),
	Upper: int(math.Ceil(upperBound)),
}
Copy

The Format function

Using the Format function we change the output format to make it easier to read. We create a new slice of Items called selectedItems with the length of the store variable trace. Each item we decided to add an item to the knapsack is added to the new slice as an Item.

}).Format(func(s store.Store) any {
selectedItems := make([]Item, 0, trace.Len(s))
for i, v := range trace.Slice(s) {
	if v {
		selectedItems = append(selectedItems, input.Items[i])
	}
}
Copy

Then we return a map that contains the selectedItems as well as the store's value and weight.

}
return map[string]any{
	"items":  selectedItems,
	"value":  value.Get(s),
	"weight": weight.Get(s),
}
Copy

Returning the solver

Finally, we return a solver for our store knapsack by using the Maximizer function passing in options that were given at the very beginning by the calling function. This solver is then executed by the run.Run function from the beginning.

return knapsack.Maximizer(opts), nil
Copy

Page last updated

Go to on-page nav menu