Multiple Knapsacks

The previous section shows how to find the optimal packing for a single knapsack. Next, we'll show how to solve the same problem for multiple knapsacks. In this case, it's common to refer to the containers as bins, rather than knapsacks, so we'll follow that convention.

Example

As in the previous section, we start with a collection of items of different weights and values, but this time we want to pack the items into five bins, each of which has a maximum weight capacity. The problem is to pack the bins so that the total value of the packed items is a maximum.

Create the data

The code below creates the data for the example.

Python

def create_data_model():
    """Create the data for the example."""
    data = {}
    weights = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36]
    values = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25]
    data['num_items'] = len(weights)
    data['all_items'] = range(data['num_items'])
    data['weights'] = weights
    data['values'] = values
    data['bin_capacities'] = [100, 100, 100, 100, 100]
    data['num_bins'] = len(data['bin_capacities'])
    data['all_bins'] = range(data['num_bins'])
    return data

C++

struct DataModel {
  const std::vector<int> weights = {{      48,
      30,
      42,
      36,
      36,
      48,
      42,
      42,
      36,
      24,
      30,
      30,
      42,
      36,
      36,
  }};
  const std::vector<int> values = {
      {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25}};
  const int num_items = weights.size();
  const int total_value = accumulate(values.begin(), values.end(), 0);
  const std::vector<int> kBinCapacities = {{100, 100, 100, 100, 100}};
  const int kNumBins = 5;
};

Java

static class DataModel {
  int[] items = new int[] {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36};
  int[] values = new int[] {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25};
  int[] binCapacities = new int[] {100, 100, 100, 100, 100};
  int numItems = items.length;
  int numBins = 5;
}
  final DataModel data = new DataModel();

The data includes the following:

  • weights: A vector containing the weights of the items.
  • values: A vector containing the values of the items.
  • capacities: A vector with five entries, the capacities of the bins.

In this example, all the bins have the same capacity, but that need not be true in general.

Create the variables

The following code creates the variables for the program.

Python

x = {}
for idx in data['all_items']:
    for b in data['all_bins']:
        x[(idx, b)] = model.NewIntVar(0, 1, 'x_%i_%i' % (idx, b))
max_value = sum(data['values'])
# value[b] is the value of bin b when packed.
value = [
    model.NewIntVar(0, max_value, 'value_%i' % b) for b in data['all_bins']
]
for b in data['all_bins']:
    model.Add(value[b] == sum(
        x[(i, b)] * data['values'][i] for i in data['all_items']))

C++

// Main variables.
std::vector<std::vector<IntVar>> x(data.num_items);
for (int i = 0; i < data.num_items; ++i) {
  for (int b = 0; b < data.kNumBins; ++b) {
    x[i].push_back(cp_model.NewIntVar({0, 1}));
  }
}

// Load variables.
std::vector<IntVar> load(data.kNumBins);
std::vector<IntVar> value(data.kNumBins);
for (int b = 0; b < data.kNumBins; ++b) {
  load[b] = cp_model.NewIntVar({0, data.kBinCapacities[b]});
  value[b] = cp_model.NewIntVar({0, data.total_value});
}

// Links load and x.
for (int b = 0; b < data.kNumBins; ++b) {
  LinearExpr weightsExpr;
  LinearExpr valuesExpr;
  for (int i = 0; i < data.num_items; ++i) {
    weightsExpr.AddTerm(x[i][b], data.weights[i]);
    valuesExpr.AddTerm(x[i][b], data.values[i]);
  }
  cp_model.AddEquality(weightsExpr, load[b]);
  cp_model.AddEquality(valuesExpr, value[b]);
}

Java

IntVar[][] x = new IntVar[data.numItems][data.numBins];
for (int i = 0; i < data.numItems; ++i) {
  for (int b = 0; b < data.numBins; ++b) {
    x[i][b] = model.newIntVar(0, 1, "x_" + i + "_" + b);
  }
}
// Main variables.
// Load and value variables.
IntVar[] load = new IntVar[data.numBins];
IntVar[] value = new IntVar[data.numBins];
for (int b = 0; b < data.numBins; ++b) {
  load[b] = model.newIntVar(0, data.binCapacities[b], "load_" + b);
  value[b] = model.newIntVar(0, totalValue, "value_" + b);
}

// Links load and value with x.
int[] sizes = new int[data.numItems];
for (int i = 0; i < data.numItems; ++i) {
  sizes[i] = data.items[i];
}
for (int b = 0; b < data.numBins; ++b) {
  IntVar[] vars = new IntVar[data.numItems];
  for (int i = 0; i < data.numItems; ++i) {
    vars[i] = x[i][b];
  }
  model.addEquality(LinearExpr.scalProd(vars, data.items), load[b]);
  model.addEquality(LinearExpr.scalProd(vars, data.values), value[b]);
}

The main variables in the Python code are the following:

  • x[(idx, b)]: A 0-1 variable that is 1 if the item with index idx is placed in bin b.
  • value[b]: The total value of the items in bin b when it is packed.

value[b] is defined to be in the range from 0 to max_value, which is the sum of the values of all items. max_value is simply a convenient way to provide an upper bound for the total value of any bin.

The C++ and Java variables are similar, but also include load variables (as a convenience).

The code also defines the relationship between the variables. For example,

for b in data['all_bins']:
    model.Add(value[b] == sum(
        x[(i, b)] * data['values'][i] for i in data['all_items']))

specifies that value[b] is the sum of the values of all items in bin b.

Create the constraints

The following code creates the constraints for the problem:

  • Each item can be placed in at most one bin (just a technical requirement on the variables x[idx, b]).
  • The total weight packed in each bin can't exceed its capacity.

Python

# Each item can be in at most one bin.
for idx in data['all_items']:
    model.Add(sum(x[idx, b] for b in data['all_bins']) <= 1)

# The amount packed in each bin cannot exceed its capacity.
for b in data['all_bins']:
    model.Add(
        sum(x[(i, b)] * data['weights'][i]
            for i in data['all_items']) <= data['bin_capacities'][b])

C++

// Each item can be in at most one bin.
for (int i = 0; i < data.num_items; ++i) {
  LinearExpr expr;
  for (int b = 0; b < data.kNumBins; ++b) {
    expr.AddTerm(x[i][b], 1);
  }
  cp_model.AddLessOrEqual(expr, 1);
}

Java

// Each item can be in at most one bin.
// Place all items.
for (int i = 0; i < data.numItems; ++i) {
  IntVar[] vars = new IntVar[data.numBins];
  for (int b = 0; b < data.numBins; ++b) {
    vars[b] = x[i][b];
  }
  model.addLessOrEqual(LinearExpr.sum(vars), 1);
}

The following code prints the solution once the solver is called.

Python

def print_solutions(data, solver, x):
    """Display the solution."""
    total_weight = 0
    total_value = 0
    for b in data['all_bins']:
        print('Bin', b, '\n')
        bin_weight = 0
        bin_value = 0
        for idx, val in enumerate(data['weights']):
            if solver.Value(x[(idx, b)]) > 0:
                print('Item', idx, '-  Weight:', val, ' Value:',
                      data['values'][idx])
                bin_weight += val
                bin_value += data['values'][idx]
        print('Packed bin weight:', bin_weight)
        print('Packed bin value:', bin_value, '\n')
        total_weight += bin_weight
        total_value += bin_value
    print('Total packed weight:', total_weight)
    print('Total packed value:', total_value)

C++

void PrintSolution(const DataModel data,
                   const std::vector<std::vector<IntVar>> x,
                   const std::vector<IntVar> load,
                   const std::vector<IntVar> value,
                   const CpSolverResponse response) {
  for (int b = 0; b < data.kNumBins; ++b) {
    LOG(INFO) << "Bin " << b;
    LOG(INFO);
    for (int i = 0; i < data.num_items; ++i) {
      if (SolutionIntegerValue(response, x[i][b]) > 0) {
        LOG(INFO) << "Item " << i << "  -  Weight: " << data.weights[i]
                  << " Value: " << data.values[i];
      }
    }
    LOG(INFO) << "Packed bin weight: "
              << SolutionIntegerValue(response, load[b]);
    LOG(INFO) << "Packed bin value: "
              << SolutionIntegerValue(response, value[b]);
    LOG(INFO);
  }
  LOG(INFO) << "Total packed weight: "
            << SolutionIntegerValue(response, LinearExpr::Sum(load));
  LOG(INFO) << "Total packed value: "
            << SolutionIntegerValue(response, LinearExpr::Sum(value));
}

Java

  static void printSolution(
      DataModel data, CpSolver solver, IntVar[][] x, IntVar[] load, IntVar[] value) {
    System.out.printf("Optimal objective value: %f%n", solver.objectiveValue());
    System.out.println();
    long packedWeight = 0;
    long packedValue = 0;
    for (int b = 0; b < data.numBins; ++b) {
      System.out.println("Bin " + b);
      for (int i = 0; i < data.numItems; ++i) {
        if (solver.value(x[i][b]) > 0) {
          System.out.println(
              "Item " + i + "  -  Weight: " + data.items[i] + "  Value: " + data.values[i]);
        }
      }
      System.out.println("Packed bin weight: " + solver.value(load[b]));
      packedWeight = packedWeight + solver.value(load[b]);
      System.out.println("Packed bin value: " + solver.value(value[b]) + "\n");
      packedValue = packedValue + solver.value(value[b]);
    }
    System.out.println("Total packed weight: " + packedWeight);
    System.out.println("Total packed value: " + packedValue);
  }

  public static void main(String[] args) {
    // Instantiate the data problem.
    final DataModel data = new DataModel();
    int totalValue = 0;
    for (int i = 0; i < data.numItems; ++i) {
      totalValue = totalValue + data.values[i];
    }

    CpModel model = new CpModel();

    IntVar[][] x = new IntVar[data.numItems][data.numBins];
    for (int i = 0; i < data.numItems; ++i) {
      for (int b = 0; b < data.numBins; ++b) {
        x[i][b] = model.newIntVar(0, 1, "x_" + i + "_" + b);
      }
    }
    // Main variables.
    // Load and value variables.
    IntVar[] load = new IntVar[data.numBins];
    IntVar[] value = new IntVar[data.numBins];
    for (int b = 0; b < data.numBins; ++b) {
      load[b] = model.newIntVar(0, data.binCapacities[b], "load_" + b);
      value[b] = model.newIntVar(0, totalValue, "value_" + b);
    }

    // Links load and value with x.
    int[] sizes = new int[data.numItems];
    for (int i = 0; i < data.numItems; ++i) {
      sizes[i] = data.items[i];
    }
    for (int b = 0; b < data.numBins; ++b) {
      IntVar[] vars = new IntVar[data.numItems];
      for (int i = 0; i < data.numItems; ++i) {
        vars[i] = x[i][b];
      }
      model.addEquality(LinearExpr.scalProd(vars, data.items), load[b]);
      model.addEquality(LinearExpr.scalProd(vars, data.values), value[b]);
    }

    // Each item can be in at most one bin.
    // Place all items.
    for (int i = 0; i < data.numItems; ++i) {
      IntVar[] vars = new IntVar[data.numBins];
      for (int b = 0; b < data.numBins; ++b) {
        vars[b] = x[i][b];
      }
      model.addLessOrEqual(LinearExpr.sum(vars), 1);
    }
    // Maximize sum of load.
    model.maximize(LinearExpr.sum(value));

    CpSolver solver = new CpSolver();
    CpSolverStatus status = solver.solve(model);

    System.out.println("Solve status: " + status);
    if (status == CpSolverStatus.OPTIMAL) {
      printSolution(data, solver, x, load, value);
    }
  }

  private MultipleKnapsackSat() {}
}

Note that if solver.Value(x[(idx, b)]) is positive only if x[(idx, b)] is in the solution, so code displays the packed items, and computes the total value and weight of the packed bins.

Call the solver

The following code calls the CP-SAT solver and passes the result to the solution printer.

Python

status = solver.Solve(model)
    if status == cp_model.OPTIMAL:
        print_solutions(data, solver, x)


if __name__ == '__main__':
    main()

C++

const CpSolverResponse response = Solve(cp_model.Build());
PrintSolution(data, x, load, value, response);

Java

CpSolver solver = new CpSolver();
CpSolverStatus status = solver.solve(model);
System.out.println("Solve status: " + status);
if (status == CpSolverStatus.OPTIMAL) {
  printSolution(data, solver, x, load, value);
}

The program first initializes the solver, and then calls it by status = solver.Solve(). packed_items is a list of the optimal packed items. Similarly, packed_weights are the weights of the packed items.

Output of the program

When you run the program, it returns the following output.

Bin 0

Item 1 -  Weight: 30  Value: 30
Item 10 -  Weight: 30  Value: 45
Item 13 -  Weight: 36  Value: 30
Packed bin weight: 96
Packed bin value: 105 

Bin 1 

Item 4 -  Weight: 36  Value: 35
Item 5 -  Weight: 48  Value: 30
Packed bin weight: 84
Packed bin value: 65 

Bin 2 

Item 2 -  Weight: 42  Value: 25
Item 12 -  Weight: 42  Value: 20
Packed bin weight: 84
Packed bin value: 45 

Bin 3 

Item 7 -  Weight: 42  Value: 40
Item 8 -  Weight: 36  Value: 30
Packed bin weight: 78
Packed bin value: 70 

Bin 4 

Item 3 -  Weight: 36  Value: 50
Item 9 -  Weight: 24  Value: 35
Item 14 -  Weight: 36  Value: 25
Packed bin weight: 96
Packed bin value: 110

Total packed weight: 438
Total packed value: 395

Complete programs

The complete programs for multiple knapsacks are shown below.

Python

"""Solves a multiple knapsack problem using the CP-SAT solver."""

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function

from ortools.sat.python import cp_model



def create_data_model():
    """Create the data for the example."""
    data = {}
    weights = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36]
    values = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25]
    data['num_items'] = len(weights)
    data['all_items'] = range(data['num_items'])
    data['weights'] = weights
    data['values'] = values
    data['bin_capacities'] = [100, 100, 100, 100, 100]
    data['num_bins'] = len(data['bin_capacities'])
    data['all_bins'] = range(data['num_bins'])
    return data




def print_solutions(data, solver, x):
    """Display the solution."""
    total_weight = 0
    total_value = 0
    for b in data['all_bins']:
        print('Bin', b, '\n')
        bin_weight = 0
        bin_value = 0
        for idx, val in enumerate(data['weights']):
            if solver.Value(x[(idx, b)]) > 0:
                print('Item', idx, '-  Weight:', val, ' Value:',
                      data['values'][idx])
                bin_weight += val
                bin_value += data['values'][idx]
        print('Packed bin weight:', bin_weight)
        print('Packed bin value:', bin_value, '\n')
        total_weight += bin_weight
        total_value += bin_value
    print('Total packed weight:', total_weight)
    print('Total packed value:', total_value)




def main():
    data = create_data_model()

    model = cp_model.CpModel()

    # Main variables.
    x = {}
    for idx in data['all_items']:
        for b in data['all_bins']:
            x[(idx, b)] = model.NewIntVar(0, 1, 'x_%i_%i' % (idx, b))
    max_value = sum(data['values'])
    # value[b] is the value of bin b when packed.
    value = [
        model.NewIntVar(0, max_value, 'value_%i' % b) for b in data['all_bins']
    ]
    for b in data['all_bins']:
        model.Add(value[b] == sum(
            x[(i, b)] * data['values'][i] for i in data['all_items']))

    # Each item can be in at most one bin.
    for idx in data['all_items']:
        model.Add(sum(x[idx, b] for b in data['all_bins']) <= 1)

    # The amount packed in each bin cannot exceed its capacity.
    for b in data['all_bins']:
        model.Add(
            sum(x[(i, b)] * data['weights'][i]
                for i in data['all_items']) <= data['bin_capacities'][b])

    # Maximize total value of packed items.
    model.Maximize(sum(value))

    solver = cp_model.CpSolver()

    status = solver.Solve(model)

    if status == cp_model.OPTIMAL:
        print_solutions(data, solver, x)


if __name__ == '__main__':
    main()

C++

#include "ortools/sat/cp_model.h"
namespace operations_research {
namespace sat {

struct DataModel {
  const std::vector<int> weights = {{      48,
      30,
      42,
      36,
      36,
      48,
      42,
      42,
      36,
      24,
      30,
      30,
      42,
      36,
      36,
  }};
  const std::vector<int> values = {
      {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25}};
  const int num_items = weights.size();
  const int total_value = accumulate(values.begin(), values.end(), 0);
  const std::vector<int> kBinCapacities = {{100, 100, 100, 100, 100}};
  const int kNumBins = 5;
};

void PrintSolution(const DataModel data,
                   const std::vector<std::vector<IntVar>> x,
                   const std::vector<IntVar> load,
                   const std::vector<IntVar> value,
                   const CpSolverResponse response) {
  for (int b = 0; b < data.kNumBins; ++b) {
    LOG(INFO) << "Bin " << b;
    LOG(INFO);
    for (int i = 0; i < data.num_items; ++i) {
      if (SolutionIntegerValue(response, x[i][b]) > 0) {
        LOG(INFO) << "Item " << i << "  -  Weight: " << data.weights[i]
                  << " Value: " << data.values[i];
      }
    }
    LOG(INFO) << "Packed bin weight: "
              << SolutionIntegerValue(response, load[b]);
    LOG(INFO) << "Packed bin value: "
              << SolutionIntegerValue(response, value[b]);
    LOG(INFO);
  }
  LOG(INFO) << "Total packed weight: "
            << SolutionIntegerValue(response, LinearExpr::Sum(load));
  LOG(INFO) << "Total packed value: "
            << SolutionIntegerValue(response, LinearExpr::Sum(value));
}

void MultipleKnapsackSat() {
  DataModel data;

  CpModelBuilder cp_model;

  // Main variables.
  std::vector<std::vector<IntVar>> x(data.num_items);
  for (int i = 0; i < data.num_items; ++i) {
    for (int b = 0; b < data.kNumBins; ++b) {
      x[i].push_back(cp_model.NewIntVar({0, 1}));
    }
  }

  // Load variables.
  std::vector<IntVar> load(data.kNumBins);
  std::vector<IntVar> value(data.kNumBins);
  for (int b = 0; b < data.kNumBins; ++b) {
    load[b] = cp_model.NewIntVar({0, data.kBinCapacities[b]});
    value[b] = cp_model.NewIntVar({0, data.total_value});
  }

  // Links load and x.
  for (int b = 0; b < data.kNumBins; ++b) {
    LinearExpr weightsExpr;
    LinearExpr valuesExpr;
    for (int i = 0; i < data.num_items; ++i) {
      weightsExpr.AddTerm(x[i][b], data.weights[i]);
      valuesExpr.AddTerm(x[i][b], data.values[i]);
    }
    cp_model.AddEquality(weightsExpr, load[b]);
    cp_model.AddEquality(valuesExpr, value[b]);
  }

  // Each item can be in at most one bin.
  for (int i = 0; i < data.num_items; ++i) {
    LinearExpr expr;
    for (int b = 0; b < data.kNumBins; ++b) {
      expr.AddTerm(x[i][b], 1);
    }
    cp_model.AddLessOrEqual(expr, 1);
  }
  // Maximize sum of load.
  cp_model.Maximize(LinearExpr::Sum(value));

  const CpSolverResponse response = Solve(cp_model.Build());

  PrintSolution(data, x, load, value, response);
}

}  // namespace sat
}  // namespace operations_research

int main() {
  operations_research::sat::MultipleKnapsackSat();

  return EXIT_SUCCESS;
}

Java

import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.IntVar;
import com.google.ortools.sat.LinearExpr;

/** Sample showing how to solve a multiple knapsack problem. */
public class MultipleKnapsackSat {
  static {
    System.loadLibrary("jniortools");
  }

  static class DataModel {
    int[] items = new int[] {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36};
    int[] values = new int[] {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25};
    int[] binCapacities = new int[] {100, 100, 100, 100, 100};
    int numItems = items.length;
    int numBins = 5;
  }

  static void printSolution(
      DataModel data, CpSolver solver, IntVar[][] x, IntVar[] load, IntVar[] value) {
    System.out.printf("Optimal objective value: %f%n", solver.objectiveValue());
    System.out.println();
    long packedWeight = 0;
    long packedValue = 0;
    for (int b = 0; b < data.numBins; ++b) {
      System.out.println("Bin " + b);
      for (int i = 0; i < data.numItems; ++i) {
        if (solver.value(x[i][b]) > 0) {
          System.out.println(
              "Item " + i + "  -  Weight: " + data.items[i] + "  Value: " + data.values[i]);
        }
      }
      System.out.println("Packed bin weight: " + solver.value(load[b]));
      packedWeight = packedWeight + solver.value(load[b]);
      System.out.println("Packed bin value: " + solver.value(value[b]) + "\n");
      packedValue = packedValue + solver.value(value[b]);
    }
    System.out.println("Total packed weight: " + packedWeight);
    System.out.println("Total packed value: " + packedValue);
  }

  public static void main(String[] args) {
    // Instantiate the data problem.
    final DataModel data = new DataModel();
    int totalValue = 0;
    for (int i = 0; i < data.numItems; ++i) {
      totalValue = totalValue + data.values[i];
    }

    CpModel model = new CpModel();

    IntVar[][] x = new IntVar[data.numItems][data.numBins];
    for (int i = 0; i < data.numItems; ++i) {
      for (int b = 0; b < data.numBins; ++b) {
        x[i][b] = model.newIntVar(0, 1, "x_" + i + "_" + b);
      }
    }
    // Main variables.
    // Load and value variables.
    IntVar[] load = new IntVar[data.numBins];
    IntVar[] value = new IntVar[data.numBins];
    for (int b = 0; b < data.numBins; ++b) {
      load[b] = model.newIntVar(0, data.binCapacities[b], "load_" + b);
      value[b] = model.newIntVar(0, totalValue, "value_" + b);
    }

    // Links load and value with x.
    int[] sizes = new int[data.numItems];
    for (int i = 0; i < data.numItems; ++i) {
      sizes[i] = data.items[i];
    }
    for (int b = 0; b < data.numBins; ++b) {
      IntVar[] vars = new IntVar[data.numItems];
      for (int i = 0; i < data.numItems; ++i) {
        vars[i] = x[i][b];
      }
      model.addEquality(LinearExpr.scalProd(vars, data.items), load[b]);
      model.addEquality(LinearExpr.scalProd(vars, data.values), value[b]);
    }

    // Each item can be in at most one bin.
    // Place all items.
    for (int i = 0; i < data.numItems; ++i) {
      IntVar[] vars = new IntVar[data.numBins];
      for (int b = 0; b < data.numBins; ++b) {
        vars[b] = x[i][b];
      }
      model.addLessOrEqual(LinearExpr.sum(vars), 1);
    }
    // Maximize sum of load.
    model.maximize(LinearExpr.sum(value));

    CpSolver solver = new CpSolver();
    CpSolverStatus status = solver.solve(model);

    System.out.println("Solve status: " + status);
    if (status == CpSolverStatus.OPTIMAL) {
      printSolution(data, solver, x, load, value);
    }
  }

  private MultipleKnapsackSat() {}
}