Knapsack Problem With the Stride Hybrid Solver

A collection of $n$ items is to be shipped, where each item has a weight $w_i$ and a value $v_i$. The goal is to pack a shipping container such that the total weight does not exceed the capacity $W$, and at most two items can be included in the container. Determine which items should be selected to maximize the total value of the container. Let $x_i$ represent whether item $i$ is in included in the container or not.

• Objective: Maximize the total value of the container

$$ \min - \sum_{i=0}^{n-1} v_i x_i $$

• Constraint 1: Total weight of the shipped container should not exceed the capacity weight

$$ \sum_{i=0}^{n-1} w_i x_i \leq W$$

• Constraint 2: At most two items can be included in the container

$$ \sum_{i=0}^{n-1} x_i \leq 2$$

This is an example of the knapsack problem. In this exercise, you will build the problem using the Stride hybrid solver. Open the knapsack.py code file. There is an array of binary variable symbols for five items. The value and weight of each item is defined in the values and weights constant symbols. The maximum capacity of the container is set to 10.

You will need to fill in the set_sampler and build_nl functions. Here are the instructions to follow:

1. In the set_sampler function:

   • Define the sampler to be used. Remember to import the required package.

2. In the build_nl function:

   • Initialize the nonlinear object called model, and import the required package.

   • Set the objective function in the nonlinear model.

   • Add the two constraints to the nonlinear model.