Improving problem reduction for 0-1 multidimensional knapsack problems with valid inequalities

DOI10.1016/J.COR.2016.01.013MaRDI QIDQ342340zbMATH OpenOpenAlexFDO

Authors Hanyu Gu

Publication date 17 November 2016

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

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

zbMATH Keywords

heuristic algorithmcore problemglobal lifted cover inequalitiesmultidimensional knapsack problem

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Recommendations

• Problem reduction heuristic for the 0-1 multidimensional knapsack problem
• Improved core problem based heuristics for the 0/1 multi-dimensional knapsack problem
• Solving the multidimensional multiple-choice knapsack problem by constructing convex hulls
• Valid inequalities for the multi-dimensional multiple-choice 0-1 knapsack problem
• Fast, effective heuristics for the 0-1 multi-dimensional knapsack problem

Cites work

• scientific article; zbMATH DE number 3614502 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• scientific article; zbMATH DE number 1416629 (Why is no real title available?)
• A New Algorithm for the 0-1 Knapsack Problem
• A genetic algorithm for the multidimensional knapsack problem
• A geometric study of dual gaps, with applications
• A multi-level search strategy for the 0-1 multidimensional knapsack problem
• A survey of effective heuristics and their application to a variety of knapsack problems
• About Lagrangian methods in integer optimization
• An Algorithm for Large Zero-One Knapsack Problems
• Facets of the knapsack polytope
• Geometric algorithms and combinatorial optimization
• Improved core problem based heuristics for the 0/1 multi-dimensional knapsack problem
• Improved results on the 0--1 multidimensional knapsack problem
• Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem
• New convergent heuristics for 0-1 mixed integer programming
• Problem reduction heuristic for the 0-1 multidimensional knapsack problem
• Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem
• Separation algorithms for 0-1 knapsack polytopes
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• The core concept for the Multidimensional Knapsack problem
• The multidimensional 0-1 knapsack problem -- bounds and computational aspects
• The multidimensional 0-1 knapsack problem: an overview.
• The multidimensional knapsack problem: structure and algorithms

Cited in

(3)

• Problem reduction heuristic for the 0-1 multidimensional knapsack problem
• Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
• A comprehensive empirical demonstration of the impact of choice constraints on solving generalizations of the 0–1 knapsack problem using the integer programming option of CPLEX^®

This page was built for publication: Improving problem reduction for 0-1 multidimensional knapsack problems with valid inequalities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q342340)