Problem reduction heuristic for the \(0\)-\(1\) multidimensional knapsack problem

DOI10.1016/j.cor.2010.06.009zbMath1251.90281MaRDI QIDQ1761939

Yong Kun Cho, James T. Moore, Raymond R. Hill

Publication date: 15 November 2012

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2010.06.009

zbMATH Keywords

heuristic optimization; design of algorithms; core problem; multi-dimensional knapsack problem

Mathematics Subject Classification ID

90C10: Integer programming

90C59: Approximation methods and heuristics in mathematical programming

Related Items

Solving large-scale multidimensional knapsack problems with a new binary harmony search algorithm, Improving problem reduction for 0-1 multidimensional knapsack problems with valid inequalities, A theoretical and empirical investigation on the Lagrangian capacities of the \(0\)-\(1\) multidimensional knapsack problem, Solving large 0-1 multidimensional knapsack problems by a new simplified binary artificial fish swarm algorithm, Solving the multidimensional knapsack problems with generalized upper bound constraints by the adaptive memory projection method, Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems, A family of composite discrete bivariate distributions with uniform marginals for simulating realistic and challenging optimization-problem instances

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• The multidimensional 0-1 knapsack problem -- bounds and computational aspects
• Heuristics for the 0-1 multidimensional knapsack problem
• A genetic algorithm for the multidimensional knapsack problem
• The core concept for the Multidimensional Knapsack problem
• Multivariate composite distributions for coefficients in synthetic optimization problems
• Greedy algorithm for the general multidimensional knapsack problem
• Core Problems in Knapsack Algorithms
• Computationally Manageable Combinational Auctions
• Combinatorial Auctions: A Survey
• Synthetic Optimization Problem Generation: Show Us the Correlations!
• An Approximate Dynamic Programming Approach to Multidimensional Knapsack Problems
• The Effects of Coefficient Correlation Structure in Two-Dimensional Knapsack Problems on Solution Procedure Performance
• Some integer programs arising in the design of main frame computers
• On the Solution of Discrete Programming Problems
• Solving 0-1 Integer Programming Problems Arising from Large Scale Planning Models
• A heuristic with tie breaking for certain 0–1 integer programming models
• A heuristic solution procedure for the multiconstraint zero-one knapsack problem
• A New Algorithm for the 0-1 Knapsack Problem
• New Greedy-Like Heuristics for the Multidimensional 0-1 Knapsack Problem
• An Algorithm for Large Zero-One Knapsack Problems
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• A recursive branch and bound algorithm for the multidimensional knapsack problem
• A Simplified Algorithm for Obtaining Approximate Solutions to Zero-One Programming Problems
• A Branch and Bound Method for the Multiconstraint Zero-One Knapsack Problem
• Needed: An Empirical Science of Algorithms
• A multidimensional knapsack model for asset-backed securitization
• The Theory and Computation of Knapsack Functions
• Experimental evaluation of heuristic optimization algorithms: A tutorial