Strong RLT1 bounds from decomposable Lagrangean relaxation for some quadratic \(0-1\) optimization problems with linear constraints

DOI10.1007/s10479-018-3092-8zbMath1437.90104OpenAlexW2901978330WikidataQ128904476 ScholiaQ128904476MaRDI QIDQ2178343

Monique Guignard

Publication date: 11 May 2020

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

Full work available at URL: https://doi.org/10.1007/s10479-018-3092-8

zbMATH Keywords

Lagrangean relaxationquadratic knapsack problemgeneralized quadratic assignment problemcrossdock door assignment probleminteger linearization propertyRLT bounds

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Discrete location and assignment (90B80) Boolean programming (90C09)

Related Items

Polynomial-size formulations and relaxations for the quadratic multiple knapsack problem

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods
• A survey for the quadratic assignment problem
• A level-2 reformulation-linearization technique bound for the quadratic assignment problem
• Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the reformulation-linearization technique
• An algorithm for the generalized quadratic assignment problem
• Linear programming for the \(0-1\) quadratic knapsack problem
• Surrogate gradient algorithm for Lagrangian relaxation
• Location, scheduling, design and integer programming
• Reoptimization in Lagrangian methods for the \(0\)-\(1\) quadratic knapsack problem
• An effective line search for the subgradient method
• Lagrangean relaxation. (With comments and rejoinder).
• Convergence of the surrogate Lagrangian relaxation method
• A Level-3 Reformulation-Linearization Technique-Based Bound for the Quadratic Assignment Problem
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• Lagrangean decomposition: A model yielding stronger lagrangean bounds
• Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
• Exact Solution of the Quadratic Knapsack Problem