Hüseyin Uğur Yıldız

Writing

A 30,000-variable knapsack, solved on a GPU in ten seconds

1 min read
  • Operations Research
  • GPU Optimization
  • Integer Programming

NVIDIA cuOpt was evaluated on a large-scale Multi-Dimensional Knapsack Problem (MKP) with 30K binary variables and 10 knapsack constraints (~300k nonzeros).

The model was solved on an NVIDIA Tesla T4 GPU under a 10-second time limit, yielding a feasible solution with a ~0.035% relative MIP gap.

mkp.py — a 54-line Python script building the multi-dimensional knapsack model with cuopt.linear_programming: 30000 binary variables and 10 capacity constraints over a random instance, a maximize objective, a 10-second time limit, and a print of status, objective value, MIP gap, and wall-clock time
The cuOpt implementation used for this experiment.