Abstract This package implements BOCS (Baptista & Poloczek, ICML 2018) for Optuna. BOCS optimizes expensive black-box functions over binary decisions, for example which features, components or assets to include.
In each trial, BOCS:
fits a second-order model of the objective, f(x) = a_0 + sum_j a_j x_j + sum_{i<j} a_ij x_i x_j, whose coefficients have a sparsity-inducing horseshoe prior, sampled with a Gibbs sampler; draws one coefficient vector from the posterior (Thompson sampling); proposes the binary point that maximizes it.
Abstract The Multi-dimensional Knapsack Problem (MKP) is a fundamental combinatorial optimization problem that generalizes the classic knapsack problem to multiple dimensions. In this problem, each item has multiple attributes (e.g., weight, volume, size) and the goal is to maximize the total value of selected items while satisfying constraints on each attribute. Despite its conceptual simplicity, the MKP is NP-hard and appears frequently in real-world applications, such as resource allocation, capital budgeting, and project selection, as remarked in recent surveys e.