Iterative semi-continuous relaxation heuristics for the multiple-choice multidimensional knapsack problem

DOI10.1016/j.cor.2010.12.016zbMath1251.90277OpenAlexW2039844201MaRDI QIDQ1761941

Raïd Mansi, Christophe Wilbaut, Igor Crévits, Saïd Hanafi

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.12.016

zbMATH Keywords

hybrid method\(0\)-\(1\) mixed integer programmingmultiple-choice multidimensional knapsack problemsemi-continuous relaxation

Mathematics Subject Classification ID

Integer programming (90C10) Mixed integer programming (90C11) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Numerical methods of relaxation type (49M20)

Related Items (6)

A ``reduce and solve approach for the multiple-choice multidimensional knapsack problem ⋮ Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems ⋮ A fuzzy multidimensional multiple-choice knapsack model for project portfolio selection using an evolutionary algorithm ⋮ A Core-Based Exact Algorithm for the Multidimensional Multiple Choice Knapsack Problem ⋮ A two-phase kernel search variant for the multidimensional multiple-choice knapsack problem ⋮ An iterative pseudo-gap enumeration approach for the multidimensional multiple-choice knapsack problem

Uses Software

• CPLEX

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved convergent heuristics for the 0-1 multidimensional knapsack problem
• Solving multidimensional knapsack problems with generalized upper bound constraints using critical event tabu search
• Hard multidimensional multiple choice knapsack problems, an empirical study
• The multidimensional 0-1 knapsack problem -- bounds and computational aspects
• A grasp-knapsack hybrid for a nurse-scheduling problem
• Hybrid algorithms for the multiple-choice multi-dimensional knapsack problem
• A multi-level search strategy for the 0-1 multidimensional knapsack problem
• A column generation method for the multiple-choice multi-dimensional knapsack problem
• Efficient algorithms for the capacitated concentrator location problem
• An algorithm for the solution of the 0-1 knapsack problem
• Local branching
• Exploiting problem structure in a genetic algorithm approach to a nurse rostering problem
• Exploring relaxation induced neighborhoods to improve MIP solutions
• Variable neighborhood decomposition search
• New convergent heuristics for 0-1 mixed integer programming
• Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem
• A best first search exact algorithm for the multiple-choice multidimensional knapsack problem
• New greedy heuristics for the multiple-choice multi-dimensional knapsack problem
• Parametric tabu-search for mixed integer programs
• A reactive local search-based algorithm for the multiple-choice multi-dimensional knapsack problem
• Variable neighbourhood decomposition search for \(0\)-\(1\) mixed integer programs
• Heuristics for determining the number of warehouses for storing non-compatible products
• A survey of effective heuristics and their application to a variety of knapsack problems
• An Exact Algorithm for the Multiple-Choice Multidimensional Knapsack Based on the Core
• A Simplified Algorithm for Obtaining Approximate Solutions to Zero-One Programming Problems
• Surrogate Constraint Duality in Mathematical Programming
• Preprocessing and Probing Techniques for Mixed Integer Programming Problems
• Une approche hybride pour le sac à dos multidimensionnel en variables 0–1
• Heuristic algorithms for the multiple-choice multidimensional knapsack problem
• A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem
• Surrogate Constraints
• A Shrinking Boundary Algorithm for Discrete System Models
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II
• Canonical Cuts on the Unit Hypercube
• Budgeting with bounded multiple-choice constraints.

This page was built for publication: Iterative semi-continuous relaxation heuristics for the multiple-choice multidimensional knapsack problem