Knapsacks

Overview

A knapsack is a bin-packing problem, in which the goal is to maximize the total value of items in (typically) a single bin. In this documentation you'll learn how to use OR-Tools to solve knapsack problems.

A simple example

Here's a graphical depiction of a knapsack problem:

In the above figure, 50 items are packed into a bin. Each item has a value (the number on the item) and a weight (roughly proportional to the area of the item). The bin is declared to have a capacity of 850, and our goal is to find the set of items that will maximize the total value without exceeding the capacity.

We'll demonstrate how to compute solutions with the Python and Java interfaces to OR-Tools.

Whatever language you use, the process is the same:

  • Create an instance of KnapsackSolver.
  • Declare the values, weights, and capacities.
  • Initialize the solver with that data.
  • Call the Solve() method.
  • Display the result.

Before solving this problem, we'll show how to solve an even simpler knapsack problem, in which the value of each object equals its weight. In this case, the problem is simply to pack the bin with items whose total weight is as large as possible. The following sections describe a Python program that solves this problem.

Data for the problem

The code below creates the data for the problem.

  weights = [[565, 406, 194, 130, 435, 367, 230, 315, 393,
              125, 670, 892, 600, 293, 712, 147, 421, 255]]
  capacities = [850]
  values = weights[0]

The vector weights contains the weights of the items. The vector capacities has just one entry, 850, which is the capacity of the knapsack. (In problems with multiple bins, each entry of capacities contains the capacity of the corresponding bin.) The solver also requires a vector of values, which is the same weights in this case.

Creating the solver

The following code creates the solver for the problem.

from ortools.algorithms import pywrapknapsack_solver

def main():
  # Create the solver.
  solver = pywrapknapsack_solver.KnapsackSolver(
      pywrapknapsack_solver.KnapsackSolver.
      KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER,
      'test')

The program uses the knapsack dynamic programming solver — a specialized solver for the knapsack problem. To create an instance of the solver, the program imports pywrapknapsack_solver, a Python wrapper for the C++ solver, KnapsackSolver, and then calls pywrapknapsack_solver with the KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER option.

Note: KnapsackSolver only accepts integer values for the weights and values. However, Using a solver with non-integer data shows how to use the solver if your data contains non-integer values.

While you can solve the knapsack problem with other OR-Tools solvers, such as the mixed integer programming solver, the knapsack dynamic programming solver can solve it faster.

Invoking the solver

The following code invokes the solver and prints the output.

  solver.Init(values, weights, capacities)
  computed_value = solver.Solve()

  packed_items = [x for x in range(0, len(weights[0]))
                    if solver.BestSolutionContains(x)]
  packed_weights = [weights[0][i] for i in packed_items]

  print("Packed items: ", packed_items)
  print("Packed weights: ", packed_weights)
  print("Total weight (same as total value): ", computed_value)

The program first initializes the solver, and then calls it by computed_value = solver.Solve(). The total value of the optimal solution is computed_value, which is the same as the total weight in this case. The program then gets the indices of the packed items in the solution by the following command:

packed_items = [x for x in range(0, len(weights[0]))
                  if solver.BestSolutionContains(x)]
Since solver.BestSolutionContains(x) returns TRUE if the item x is included in the solution, packed_items is a list of the optimal packed items. Similarly, packed_weights are the weights of the packed items.

Output of the program

Here is the output of the program.

$ python my_projects/one_dim_knapsack.py
Packed items:  [2, 3, 6, 13]
Packed weights:  [194, 130, 230, 293]
Total weight (same as total value):  847

Using a solver with non-integer data

If your problem involves non-integer data, you can still use the knapsack solver (or any other solver that only accepts integer inputs) as follows. Before invoking the solver, multiply all the data (including the capacities) by a suitably large integer and then round. For instance, if your weights are 3.14159 and 2.71828, multiply by 10000 to make them 314159 and 271828. Then solve and divide the packed weights in the solution by the same number.

The entire program

The entire program to solve the knapsack problem is shown below.

from __future__ import print_function
from ortools.algorithms import pywrapknapsack_solver

def main():
  # Create the solver.
  solver = pywrapknapsack_solver.KnapsackSolver(
      pywrapknapsack_solver.KnapsackSolver.
      KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER,
      'test')

  weights = [[565, 406, 194, 130, 435, 367, 230, 315, 393,
              125, 670, 892, 600, 293, 712, 147, 421, 255]]
  capacities = [850]
  values = weights[0]
  solver.Init(values, weights, capacities)
  computed_value = solver.Solve()

  packed_items = [x for x in range(0, len(weights[0]))
                    if solver.BestSolutionContains(x)]
  packed_weights = [weights[0][i] for i in packed_items]

  print("Packed items: ", packed_items)
  print("Packed weights: ", packed_weights)
  print("Total weight (same as total value): ", computed_value)
if __name__ == '__main__':
  main()

Back to the original problem

Next, we show how to solve the original problem given above, in which the values of the items are different from their. weights. The constraint is the same as before — the total weight of packed items cannot exceed the knapsack's capacity. But the goal now is to maximize the total value of the packed items, rather than the total weight.

The following code shows the essential differences between solving this problem as opposed to the previous one.

  values = [360, 83, 59, 130, 431, 67, 230, 52, 93,
            125, 670, 892, 600, 38, 48, 147, 78, 256,
            63, 17, 120, 164, 432, 35, 92, 110, 22,
            42, 50, 323, 514, 28, 87, 73, 78, 15,
            26, 78, 210, 36, 85, 189, 274, 43, 33,
            10, 19, 389, 276, 312]

  weights = [[7, 0, 30, 22, 80, 94, 11, 81, 70,
              64, 59, 18, 0, 36, 3, 8, 15, 42,
              9, 0, 42, 47, 52, 32, 26, 48, 55,
              6, 29, 84, 2, 4, 18, 56, 7, 29,
              93, 44, 71, 3, 86, 66, 31, 65, 0,
              79, 20, 65, 52, 13]]

  capacities = [850]

  solver.Init(values, weights, capacities)
  computed_value = solver.Solve()

  packed_items = [x for x in range(0, len(weights[0]))
                  if solver.BestSolutionContains(x)]
  packed_weights = [weights[0][i] for i in packed_items]
  total_weight= sum(packed_weights)
  print "Packed items: ", packed_items
  print "Packed weights: ", packed_weights
  print "Total value: ", computed_value
  print "Total weight: ", total_weight

Note that values is now different from weights. In the output, we display the packed items, along with their total value and total weight.

Packed items:  [0, 1, 3, 4, 6, 10, 11, 12, 14, 15, 16, 17, 18, 19, 21, 22, 24, 27, 28, 29, 30,
                31, 32, 34, 38, 39, 41, 42, 44, 47, 48, 49]
Packed weights:  [7, 0, 22, 80, 11, 59, 18, 0, 3, 8, 15, 42, 9, 0, 47, 52, 26, 6, 29, 84, 2, 4,
                  18, 7, 71, 3, 66, 31, 0, 65, 52, 13]
Total value:  7534
Total weight:  850

Complete Python and Java programs

Below are complete Python and Java programs that solve the original knapsack program.

Python
from ortools.algorithms import pywrapknapsack_solver

def main():
  # Create the solver.
  solver = pywrapknapsack_solver.KnapsackSolver(
      pywrapknapsack_solver.KnapsackSolver.
      KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
      'test')
  values = [360, 83, 59, 130, 431, 67, 230, 52, 93,
            125, 670, 892, 600, 38, 48, 147, 78, 256,
            63, 17, 120, 164, 432, 35, 92, 110, 22,
            42, 50, 323, 514, 28, 87, 73, 78, 15,
            26, 78, 210, 36, 85, 189, 274, 43, 33,
            10, 19, 389, 276, 312]

  weights = [[7, 0, 30, 22, 80, 94, 11, 81, 70,
              64, 59, 18, 0, 36, 3, 8, 15, 42,
              9, 0, 42, 47, 52, 32, 26, 48, 55,
              6, 29, 84, 2, 4, 18, 56, 7, 29,
              93, 44, 71, 3, 86, 66, 31, 65, 0,
              79, 20, 65, 52, 13]]

  capacities = [850]

  solver.Init(values, weights, capacities)
  computed_value = solver.Solve()

  packed_items = [x for x in range(0, len(weights[0]))
                  if solver.BestSolutionContains(x)]
  packed_weights = [weights[0][i] for i in packed_items]
  total_weight= sum(packed_weights)
  print "Packed items: ", packed_items
  print "Packed weights: ", packed_weights
  print "Total value: ", computed_value
  print "Total weight: ", total_weight
if __name__ == '__main__':
  main()
Java
package com.google.ortools.samples;

import com.google.ortools.algorithms.KnapsackSolver;

public class Knapsack {

  static {
    System.loadLibrary("jniortools");
  }

  private static void solve() {
    KnapsackSolver solver = new KnapsackSolver(
        KnapsackSolver.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER, "test");
    final long[] profits = {360, 83, 59, 130, 431, 67, 230, 52, 93,
                            125, 670, 892, 600, 38, 48, 147, 78, 256,
                            63, 17, 120, 164, 432, 35, 92, 110, 22,
                            42, 50, 323, 514, 28, 87, 73, 78, 15,
                            26, 78, 210, 36, 85, 189, 274, 43, 33,
                            10, 19, 389, 276, 312};

    final long[][] weights = {{7, 0, 30, 22, 80, 94, 11, 81, 70,
                               64, 59, 18, 0, 36, 3, 8, 15, 42,
                               9, 0, 42, 47, 52, 32, 26, 48, 55,
                               6, 29, 84, 2, 4, 18, 56, 7, 29,
                               93, 44, 71, 3, 86, 66, 31, 65, 0,
                               79, 20, 65, 52, 13}};

    final long[] capacities = {850};

    solver.init(profits, weights, capacities);
    final long computedWeight = solver.solve();
  }

  public static void main(String[] args) throws Exception {
    Knapsack.solve();
  }
}

Enviar comentarios sobre…