Advanced greedy algorithms and surrogate constraint methods for linear and quadratic knapsack and covering problems

DOI10.1016/j.ejor.2013.04.010zbMath1317.90327OpenAlexW2098002863MaRDI QIDQ2355937

Fred Glover

Publication date: 28 July 2015

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

Full work available at URL: https://doi.org/10.1016/j.ejor.2013.04.010

zbMATH Keywords

metaheuristicstabu searchgreedy algorithmssurrogate constraintsknapsack/covering problemsmulti-start/strategic oscillation

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (4)

A multi-start iterated local search algorithm for the generalized quadratic multiple knapsack problem ⋮ An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem ⋮ An improved version of a core based algorithm for the multi-objective multi-dimensional knapsack problem: a computational study and comparison with meta-heuristics ⋮ High generalization performance structured self-attention model for knapsack problem

Uses Software

• OR-Library

Cites Work

• Unnamed Item
• Unnamed Item
• Improved convergent heuristics for the 0-1 multidimensional knapsack problem
• The multidimensional 0-1 knapsack problem -- bounds and computational aspects
• Exploiting nested inequalities and surrogate constraints
• Fast, effective heuristics for the 0-1 multi-dimensional knapsack problem
• Surrogate constraint normalization for the set covering problem
• Least-cost network topology design for a new service: An application of tabu search
• Tutorial on surrogate constraint approaches for optimization in graphs
• Improved results on the 0--1 multidimensional knapsack problem
• Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions
• Tabu search for graph partitioning
• A tabu thresholding algorithm for arc crossing minimization in bipartite graphs
• Dynamic tabu search strategies for the traveling purchaser problem
• Strategic oscillation for the quadratic multiple knapsack problem
• Greedy algorithm for the general multidimensional knapsack problem
• Surrogate Constraints in Integer Programming
• Surrogate Constraint Duality in Mathematical Programming
• Une approche hybride pour le sac à dos multidimensionnel en variables 0–1
• Tabu Thresholding: Improved Search by Nonmonotonic Trajectories
• Discrete-Variable Extremum Problems
• A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem
• Flows in Arborescences

This page was built for publication: Advanced greedy algorithms and surrogate constraint methods for linear and quadratic knapsack and covering problems