Robust Knapsack

Consider the robust knapsack problem introduced in [1, Section 6.1]. This problem seeks to optimize the selection of items under worst-case scenarios, ensuring that the knapsack’s total value is maximized while remaining feasible despite uncertainties in values.

Using the same formulation as in [1], the problem can be formulated as follows:

$$\begin{array}{r}\begin{array}{ll}\text{maximize}& c^{T}x\\ \text{subject to}& w^{T}x\le b\mathrm{\forall }w\in \mathcal{U}\\ & x\in \{0,1{\}}^n\end{array}\end{array}$$

where there are $n$ items, $x$ are the binary decision variables, their values are denoted by $c$, and their weights $w$ belong to a box uncertainty set, where the expected weights are denoted by $w_e$, and their uncertainties are captured by $\delta \delta$.

import cvxpy as cp
import numpy as np
import lropt

np.random.seed(seed=1234)

We define the constants as shown below:

n = 200 #Number of items
b = 1000 #Capacity
c = np.random.uniform(low=0., high=1., size=n) #Value of each item
w_e = np.random.uniform(low=1., high=2, size=n) #Mean weight of each item
delta = np.random.uniform(low=0., high=0.1, size=n) #Weights uncertainties

The uncertain parameter $\mathbf{p}$ is formulated using LROPT in the block below. We use the box uncertainty set, which is defined as follows:

$$\mathcal{U}=\{\mathbf{w}\mid \overline{\mathbf{w}}-\delta \le \mathbf{w}\le \overline{\mathbf{w}}+\delta \}$$

uncertainty_set = lropt.Box(rho=1, a=np.diag(delta), b=w_e)
w = lropt.UncertainParameter(n, uncertainty_set=uncertainty_set) #Uncertain parameter
x = cp.Variable(n, boolean=True) #Optimization variable

#Define and solve the problem
objective = cp.Maximize(c@x)
constraints = [w@x <= b]
prob = lropt.RobustProblem(objective=objective, constraints=constraints)
prob.solve(solver = cp.SCIP)

/Users/mj5676/Desktop/miniconda3/envs/lropt_v3/lib/python3.12/site-packages/cvxpy/utilities/torch_utils.py:61: UserWarning: torch.sparse.SparseTensor(indices, values, shape, *, device=) is deprecated.  Please use torch.sparse_coo_tensor(indices, values, shape, dtype=, device=). (Triggered internally at /Users/runner/work/pytorch/pytorch/pytorch/torch/csrc/utils/tensor_new.cpp:643.)
  return torch.sparse.FloatTensor(i, v, torch.Size(value_coo.shape)).to(dtype)

References

1. Bertsimas and Sim 2004 (https://pubsonline.informs.org/doi/abs/10.1287/opre.1030.0065)