Solving packing problems

nextmv sdk install

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 guide will walk you through our knapsack template. To get the template, simply run the following command.

nextmv sdk init -t knapsack

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

ls -v knapsack

• 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.
• 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.
• 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.

Now you can run the template with the Nextmv CLI, reading from the input.json file and writing to an output.json file. The following command shows you how to specify solver limits as well. You should obtain an output similar to the one shown.

nextmv sdk run main.go -- \
    -runner.input.path input.json \
    -runner.output.path output.json \
    -limits.duration 5s \
    -diagram.expansion.limit 1 \
    -sense 1

Note that transient fields like timestamps, duration, versions, etc. are represented with dummy values due to their dynamic nature. I.e., every time the input is run or the version is bumped, these fields will have a different value.

Now we will show you, step by step, what the code inside the main.go achieves.

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 (
	"log"
	"math"
	"sort"
	"time"

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

func main() {
	err := run.Run(solver)

The Input

But before we look into the solver function, we will examine the two structs input and item.

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

// 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"`
}

The input 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 input Capacity for adding the item).

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 input, opts store.Options) (store.Solver, error) {

When you first ran the template you passed in the parameter -runner.input.path followed by the path to an input file. This file is automatically parsed and converted to our input 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).

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])
})

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.

knapsack := store.New()
value := store.NewVar(knapsack, 0)
weight := store.NewVar(knapsack, 0)
itemIdx := store.NewVar(knapsack, -1)
for i := 0; i < len(input.Items); i++ {
	trace[i] = store.NewVar(knapsack, false)
}

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. In the following case we pass our knapsack and 0:

value := store.NewVar(knapsack, 0)

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 := 0

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.

func() bool {
	return i <= 2 && next < len(input.Items) &&
		weight.Get(s) <= input.Capacity
},

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.

changes := make([]store.Change, 0)

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.

i++

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.

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[next].Set(takeItem),
		itemIdx.Set(next),
	)
} else {

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...)

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[next].Set(takeItem),
		itemIdx.Set(next),
	)
}

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...)

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(
	func(s store.Store) bool {
		return weight.Get(s) <= input.Capacity
	}).Value(

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(
	value.Get,
).Bound(

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 calculate the upper bound:

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

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:

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)

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.

if weightNeeded <= spaceLeft {
	upperBound += val
	currentWeight += weightNeeded
} else {

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 {
	fraction := spaceLeft / weightNeeded
	upperBound += fraction * val
	break
}

Finally, we return our lower and upper bound:

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

The Format function

Using the Format function we change the output format to make it easier to read.

return store.Bounds{

The function is then defined as follows:

	return knapsack.Maximizer(opts), nil
}

// format returns a function to format the solution output.
func format(
	trace []store.Var[bool],
	value store.Var[int],
	weight store.Var[int],
	input input,
) func(s store.Store) any {
	return func(s store.Store) any {
		selectedItems := make([]item, 0, len(trace))
		for i, v := range trace {
			if v.Get(s) {
				selectedItems = append(selectedItems, input.Items[i])
			}
		}
		return map[string]any{
			"items":  selectedItems,
			"value":  value.Get(s),

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.

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

	weight store.Var[int],
	input input,
) func(s store.Store) any {
	return func(s store.Store) any {
		selectedItems := make([]item, 0, len(trace))
		for i, v := range trace {
			if v.Get(s) {
				selectedItems = append(selectedItems, input.Items[i])
			}
		}
		return map[string]any{

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.

opts.Limits.Duration = 10 * time.Second