An exact algorithm for the Knapsack problem with setup
Summary: In this paper, we study a \(0-1\) Knapsack problem with setup (KPS). One set of \(0-1\) variables represents a family setup and serves as an upper bound (UB) on another set of \(0-1\) variables representing production of a job in a family. We present a branch-and-bound algorithm to find an optimal solution to KPS. The algorithm uses a two-stage branching strategy and chooses the next candidate problem to be explored in a non-traditional way. We verify the efficiency of the algorithm through computational testing. This is the first time that an exact algorithm is applied to a KPS with 10,000 integer variables. Computational experiments show that the algorithm is especially effective when objective and constraint coefficients are uncorrelated.
- An exact approach for the 0-1 knapsack problem with setups
- Exact approaches for the knapsack problem with setups
- Knapsack problems -- an overview of recent advances. I: Single knapsack problems
- A faster exact method for large-scale knapsack problems with setup costs and times
- A dynamic programming algorithm for the knapsack problem with setup
- Exact Algorithms For The Setup Knapsack Problem
- Exact algorithm for solving knapsack problem with a single continuous variable
- A new exact algorithm for concave knapsack problems with integer variables
- LP relaxation and dynamic programming enhancing VNS for the multiple knapsack problem with setup
- Controlled Discovery and Localization of Signals via Bayesian Linear Programming
- Exact algorithm for concave knapsack problems: linear underestimation and partition method
- Exact and heuristic solution approaches for the mixed integer setup knapsack problem
This page was built for publication: An exact algorithm for the Knapsack problem with setup
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q840596)
