An iterative variable-based fixation heuristic for the 0-1 multidimensional knapsack problem

DOI10.1016/j.ejor.2008.11.036zbMath1176.90669OpenAlexW2040711437MaRDI QIDQ1042147

Saïd Hanafi, Christophe Wilbaut, Said Salhi

Publication date: 7 December 2009

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://kar.kent.ac.uk/25481/1/MultistartKent_revised_May2008__Web.pdf

zbMATH Keywords

heuristicsknapsackexact methodsfixation techniques

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59)

Related Items

Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems ⋮ Mathematical programming based heuristics for the 0--1 MIP: a survey ⋮ Corrigendum to: ``Empirical orthogonal constraint generation for multidimensional 0/1 knapsack problems ⋮ A three-phase matheuristic algorithm for the multi-day task assignment problem ⋮ Variable neighborhood search: the power of change and simplicity ⋮ Capacity allocation problem with random demands for the rail container carrier ⋮ A theoretical and empirical investigation on the Lagrangian capacities of the \(0\)-\(1\) multidimensional knapsack problem ⋮ Solving the multidimensional knapsack problems with generalized upper bound constraints by the adaptive memory projection method ⋮ Identifying redundancy in multi-dimensional knapsack constraints based on surrogate constraints ⋮ Complexity indices for the multidimensional knapsack problem ⋮ Iterative approaches for a dynamic memory allocation problem in embedded systems

Uses Software

• OR-Library

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The multidimensional 0-1 knapsack problem -- bounds and computational aspects
• Exploiting nested inequalities and surrogate constraints
• An effective VNS for the capacitated \(p\)-median problem
• A genetic algorithm for the multidimensional knapsack problem
• Reducing the number of variables in integer and linear programming problems
• A note on reducing the number of variables in integer programming problems
• Local branching
• An efficient tabu search approach for the 0-1 multidimensional knapsack problem
• Exploring relaxation induced neighborhoods to improve MIP solutions
• Improved results on the 0--1 multidimensional knapsack problem
• Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions
• New convergent heuristics for 0-1 mixed integer programming
• A survey of effective heuristics and their application to a variety of knapsack problems
• Capital Budgeting Under Uncertainty—An Integrated Approach Using Contingent Claims Analysis and Integer Programming
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• A Branch and Bound Method for the Multiconstraint Zero-One Knapsack Problem
• Preprocessing and Probing Techniques for Mixed Integer Programming Problems
• Une approche hybride pour le sac à dos multidimensionnel en variables 0–1
• Partial enumeration in heuristics for some combinatorial optimization problems
• The Theory and Computation of Knapsack Functions
• A ``logic-constrained knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite