Hybrid algorithms for the multiple-choice multi-dimensional knapsack problem
Summary: In this paper, we propose three versions of an algorithm for approximately solving large-scale \textit{multiple-choice multi-dimensional knapsack problems} (MMKP). First, an adaptation of the local branching is proposed. Second, a hybrid solution procedure is presented that is based on two complementary solution procedures: a local branching which cooperates with a column generation solution procedure. Third and last, an augmented algorithm of the last hybrid algorithm is developed. It can also be viewed as a special truncated branch-and-bound in which the first hybrid algorithm is applied to a subset of elite nodes generated according to some variables/constraint branchings. The proposed methods are analysed computationally on a set of instances from the literature and compared to the results provided by other algorithms therein. Encouraging results have been obtained.
- A column generation method for the multiple-choice multi-dimensional knapsack problem
- Heuristic algorithms for the multiple-choice multidimensional knapsack problem
- A hybrid dynamic programming/branch-and-bound algorithm for the multiple- choice knapsack problem
- scientific article; zbMATH DE number 5733644
- A best first search exact algorithm for the multiple-choice multidimensional knapsack problem
- An iterative pseudo-gap enumeration approach for the multidimensional multiple-choice knapsack problem
- Iterative semi-continuous relaxation heuristics for the multiple-choice multidimensional knapsack problem
- Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
- A best first search exact algorithm for the multiple-choice multidimensional knapsack problem
- Hybrid rounding techniques for knapsack problems
- Solving the multidimensional multiple-choice knapsack problem by constructing convex hulls
- A reactive local search-based algorithm for the multiple-choice multi-dimensional knapsack problem
- Hybrid approaches for the two-scenario max-min knapsack problem
- A hybrid distribution estimation algorithm for solving multidimensional knapsack problems
- A ``reduce and solve approach for the multiple-choice multidimensional knapsack problem
- Construct, merge, solve and adapt versus large neighborhood search for solving the multi-dimensional knapsack problem: which one works better when?
- scientific article; zbMATH DE number 5282967 (Why is no real title available?)
- scientific article; zbMATH DE number 5733644 (Why is no real title available?)
- A heuristic algorithm for resource allocation/reallocation problem
- scientific article; zbMATH DE number 1281676 (Why is no real title available?)
- Une approche hybride pour le sac à dos multidimensionnel en variables 0–1
- Heuristic algorithms for the multiple-choice multidimensional knapsack problem
- A Core-Based Exact Algorithm for the Multidimensional Multiple Choice Knapsack Problem
- A hybrid of nested partition, binary ant system, and linear programming for the multidimensional knapsack problem
- Hard multidimensional multiple choice knapsack problems, an empirical study
- A column generation method for the multiple-choice multi-dimensional knapsack problem
This page was built for publication: Hybrid algorithms for the multiple-choice multi-dimensional knapsack problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q840573)
