A heuristic algorithm for resource allocation/reallocation problem
Summary: This paper presents a 1-opt heuristic approach to solve resource allocation/reallocation problem which is known as 0/1 multichoice multidimensional knapsack problem (MMKP). The intercept matrix of the constraints is employed to find optimal or near-optimal solution of the MMKP. This heuristic approach is tested for 33 benchmark problems taken from OR library of sizes upto 7000, and the results have been compared with optimum solutions. Computational complexity is proved to be \(O(klmn^2)\) of solving heuristically MMKP using this approach. The performance of our heuristic is compared with the best state-of-art heuristic algorithms with respect to the quality of the solutions found. The encouraging results especially for relatively large-size test problems indicate that this heuristic approach can successfully be used for finding good solutions for highly constrained NP-hard problems.
- scientific article; zbMATH DE number 1728442
- Heuristic algorithms for the multiple-choice multidimensional knapsack problem
- Fast, effective heuristics for the 0-1 multi-dimensional knapsack problem
- A new polynomial time algorithm for 0-1 multiple knapsack problem based on dominant principles
- Heuristics for the 0-1 multidimensional knapsack problem
- A best first search exact algorithm for the multiple-choice multidimensional knapsack problem
- A column generation method for the multiple-choice multi-dimensional knapsack problem
- A heuristic approach for identification of redundant constraints in linear programming models
- A new polynomial time algorithm for 0-1 multiple knapsack problem based on dominant principles
- A reactive local search-based algorithm for the multiple-choice multi-dimensional knapsack problem
- A Simplified Algorithm for Obtaining Approximate Solutions to Zero-One Programming Problems
- A simulated annealing approach to the multiconstraint zero-one knapsack problem
- Advanced preprocessing techniques for linear and quadratic programming
- An Algorithm for Determining Irrelevant Constraints and all Vertices in Systems of Linear Inequalities
- Analysis of mathematical programming problems prior to applying the simplex algorithm
- Finding duplicate rows in a linear programming model
- Heuristic algorithms for the multiple-choice multidimensional knapsack problem
- scientific article; zbMATH DE number 1728442 (Why is no real title available?)
- Hybrid algorithms for the multiple-choice multi-dimensional knapsack problem
- Identifying Redundant Constraints and Implicit Equalities in Systems of Linear Constraints
- Presolve Analysis of Linear Programs Prior to Applying an Interior Point Method
- Redundancy in mathematical programming. A state-of-the-art survey
- Robust reduction of a class of large-scale linear programs
- Two direct methods in linear programming
This page was built for publication: A heuristic algorithm for resource allocation/reallocation problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q410767)
