A New Heuristic for Solving the Multichoice Multidimensional Knapsack Problem
IEEE Transactions on Systems Man and Cybernetics - Part A Systems and HumansPublished 16 August 2005
R. Parra-Hernandez, N.J. Dimopoulos
Citations116
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new heuristic for solving the multichoice multidimensional knapsack problem (MMKP) is presented, and the performance of this approach is superior to that of previous techniques.
Abstract
A new heuristic for solving the multichoice multidimensional knapsack problem (MMKP) is presented in this paper. The MMKP is first reduced to a multidimensional knapsack problem (MKP). A linear programming relaxation of the resulting MKP is solved, and a series of new values for the variables is computed. These values, pseudo-utility values, and resource value coefficients computed as well, are used in order to obtain a feasible solution for the original MMKP. Finally, the quality of the feasible solution is improved using the pseudo-utility values and the coefficient values of the objective function. Numerical results show that the performance of this approach is superior to that of previous techniques.
Keywords
Computer ScienceEngineering
Journal of the Operational Research SocietyKnapsack Problems: Algorithms and Computer Implementations
3,163 Citations1991David Connolly, Silvano Martello +1 more
This paper focuses on the part of the knapsack problem where the problem of bin packing is concerned and investigates the role of computer codes in the solution of this problem.
European Journal of Operational ResearchKnapsack problems, algorithms and computer implementations
1,413 Citations1991Jeroen De Kort
Operations ResearchGeneralized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources
1,267 Citations1963Hugh Everett
Journal of the ACMFast Approximation Algorithms for the Knapsack and Sum of Subset Problems
959 Citations1975Óscar H. Ibarra, Chul E. Kim
An algorithm is presented which finds for any 0 < e < 1 an approximate solution P satisfying (P* P)/P* < ~, where P* is the desired optimal sum.
Interior Point Algorithms
946 Citations1997Yinyu Ye
This paper presents a meta-analyses of Linear Programming Algorithms and its applications to Convex Optimization, aiming at determining the best and worst case scenarios for each of the algorithms.
Operations ResearchDiscrete-Variable Extremum Problems
913 Citations1957George B. Dantzig
This paper reviews some recent successes in the use of linear programming methods for the solution of discrete-variable extremum problems and one example of the Use of the multistage approach of dynamic programming for this purpose is discussed.
Journal of HeuristicsA Genetic Algorithm for the Multidimensional Knapsack Problem
816 Citations1998P.C. Chu, J. E. Beasley
A heuristic operator which utilises problem-specific knowledge is incorporated into the standard genetic algorithm approach and is capable of obtaining high-quality solutions for problems of various characteristics.
North-Holland mathematics studiesAlgorithms for Knapsack Problems
468 Citations1987Silvano Martello, Paolo Toth
A great variety of practical problems that are represented by a set of entities, each having an associated value, from which one or more subsets has to be selected in such a way that the sum of the values of the selected entities is maximized and some predefined conditions are presented.
Journal of the ACMApproximate Algorithms for the 0/1 Knapsack Problem
347 Citations1975Sartaj Sahni
A serms of increasingly accurate algorithms to obtain approximate solutions to the 0/1 one-dlmensmnal knapsack problem and each algorithm guarantees a certain minimal closeness to the optimal solution value.
SIAM Journal on OptimizationOn Implementing Mehrotra’s Predictor–Corrector Interior-Point Method for Linear Programming
328 Citations1992Irvin J. Lustig, Roy E. Marsten +1 more
Optimization methods & softwareSolving large-scale linear programs by interior-point methods under the Matlab<sup>∗</sup>Environment<sup>†</sup>
323 Citations1998Yin Zhang
This paper describes the implementation of a primal-dual infeasible-interior-point algorithm for large-scale linear programming under the MATLAB environment, and discusses in detail a technique for overcoming numerical instability in Cholesky factorization at the end-stage of iterations in interior-point algorithms.
Management SciencePivot and Complement–A Heuristic for 0-1 Programming
259 Citations1980Egon Balas, Clarence H. Martin
Management ScienceA Simplified Algorithm for Obtaining Approximate Solutions to Zero-One Programming Problems
246 Citations1975Yoshiaki Toyoda
The method is applicable not only to those problems associated with obtaining the optimal package of variables with the value one but also to a great variety of binary choice problems.
Mathematical ProgrammingEfficient algorithms for solving multiconstraint zero-one knapsack problems to optimality
223 Citations1985Bezalel Gavish, Hasan Pirkul
An efficient branch and bound procedure is developed, tested and compared with two previously developed optimal algorithms and can be used as a heuristic for large problems by early termination of the search tree.
A scalable solution to the multi-resource QoS problem
218 Citations2003C. Lee, John P. Lehoczky +3 more
On quality of service optimization with discrete QoS options
211 Citations2003Chen Lee, J. Lehoezky +2 more
This paper tackles the problem of maximizing system utility by allocating a single finite resource to satisfy the QoS requirements of multiple applications along multiple QoS dimensions, and presents two near-optimal algorithms to solve this problem.
Management ScienceA Mathematical Programming Model for Scheduling Nursing Personnel in a Hospital
205 Citations1972D. Warner, Juan Prawda
Initial results suggest that a linear programming formulation, with a post-optimal feasibility search scheme, may be substituted for the multiple-choice master problem.
Naval Research Logistics (NRL)A heuristic solution procedure for the multiconstraint zero-one knapsack problem
166 Citations1987Hasan Pirkul
A new heuristic procedure is proposed that makes use of surrogate duality in solving multiconstraint knapsack problems and generates good feasible solutions regardless of the problem structure.
European Journal of Operational ResearchA heuristic algorithm for the multidimensional zero-one knapsack problem
119 Citations1984Michael J. Magazine, Osman Oğuz
Computational and theoretical aspects of a new heuristic for the multidimensional zero-one knapsack problem are studied and its computational efficiency is compared with two other well-known heuristics.
Operations ResearchNew Greedy-Like Heuristics for the Multidimensional 0-1 Knapsack Problem
113 Citations1979Richard Loulou, Eleftherios Michaelides
Four heuristic methods are developed to obtain approximate solutions to the multidimensional 0-1 knapsack problem and are compared to the rigorous optimum as well as to a heuristic method of Toyoda.
PCx user guide
66 Citations1997Joseph Czyzyk, Sanjay Mehrotra +1 more
Information is given about problem formulation and the underlying algorithm, along with instructions for installing, invoking, and using the code PCx, a primal-dual interior-point code for linear programming.
Declarative scheduling for optimally graceful QoS degradation
19 Citations2002M. Moser
A mechanism for optimally graceful QoS degradation in distributed real time multimedia services, declarative scheduling is introduced and a heuristic for this knapsack problem is proposed and shown to be sufficiently efficient and accurate to implement declaratives scheduling.
SIAM Journal on OptimizationA Complexity Analysis for Interior-Point Algorithms Based on Karmarkar’s Potential Function
10 Citations1994Jun Ji, Yinyu Ye
A new complexity analysis for constant potential reduction algorithms for linear programming is considered and Karmarkar’s primal-based potential function is used, showing that for a class of linear programs the number of iterations required is at most $O( mt + n\log ( n ) )$.
Channel resource allocation/reallocation in cellular communication and linear programming
2 Citations2004R. Parra-Hernandez, N.J. Dimopoulos
An approach aiming to formulate the mobile network resource allocation problem is proposed here, where the way network resources are to be counted is defined and a constrained optimisation linear programming problem is obtained.