A modified descent method-based heuristic for binary quadratic knapsack problems with conflict graphs

DOI10.1007/S10479-019-03290-3zbMATH Open1467.90050OpenAlexW2957148222WikidataQ127464687 ScholiaQ127464687MaRDI QIDQ829173FDOQ829173

Authors: Isma Dahmani, Mhand Hifi 

Publication date: 5 May 2021

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-019-03290-3

Recommendations

• A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph
• A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts
• An improved direct descent algorithm for binary knapsack problems
• A fast algorithm for knapsack problem with conflict graph
• Approximation of knapsack problems with conflict and forcing graphs
• The Knapsack Problem with Conflict Graphs
• A branch-and-bound algorithm for the quadratic multiple knapsack problem
• The performance of the modified subgradient algorithm on solving the 0-1 quadratic Knapsack problem
• The Quadratic Multiknapsack Problem with Conflicts and Balance Constraints
• A dynamic programming heuristic for the quadratic knapsack problem

zbMATH Keywords

optimizationheuristicdescentknapsack

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• Discrete-variable extremum problems
• An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem
• Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem
• Hiding information and signatures in trapdoor knapsacks
• The Knapsack Problem with Conflict Graphs
• An efficient algorithm for the knapsack sharing problem
• A reactive local search-based algorithm for the disjunctively constrained knapsack problem

Cited In (3)

• Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
• A flow based formulation and a reinforcement learning based strategic oscillation for cross-dock door assignment
• The knapsack problem with forfeit sets

Uses Software

• GLPK
• Knapsack
• GitHub

This page was built for publication: A modified descent method-based heuristic for binary quadratic knapsack problems with conflict graphs

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