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

DOI10.1007/S10479-018-3092-8MaRDI QIDQ2178343zbMATH OpenOpenAlexWikidataFDO

Authors 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

generalized quadratic assignment problemLagrangean relaxationquadratic knapsack problemcrossdock door assignment probleminteger linearization propertyRLT bounds

Mathematics Subject Classification ID

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

Recommendations

• Convex Relaxations of (0, 1)-Quadratic Programming
• A new semidefinite relaxation for \(L_{1}\)-constrained quadratic
• Copositive relaxation beats Lagrangian dual bounds in quadratically and linearly constrained quadratic optimization problems
• Strong and total Lagrange dualities for quasiconvex programming
• Strong and total Lagrange dualities for quasiconvex programming
• Convex relaxation and Lagrangian decomposition for indefinite integer quadratic programming
• Quadratic 0–1 programming: Tightening linear or quadratic convex reformulation by use of relaxations
• On the tightness of an LP relaxation for rational optimization and its applications
• Decomposition and linearization for 0-1 quadratic programming
• Linear programming relaxation for quasiconvex programming

Cites work

• scientific article; zbMATH DE number 3152649 (Why is no real title available?)
• scientific article; zbMATH DE number 3614502 (Why is no real title available?)
• 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
• A level-2 reformulation-linearization technique bound for the quadratic assignment problem
• A level-3 reformulation-linearization technique-based bound for the quadratic assignment problem
• A survey 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
• An effective line search for the subgradient method
• Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
• Convergence of the surrogate Lagrangian relaxation method
• Exact Solution of the Quadratic Knapsack Problem
• Lagrangean decomposition: A model yielding stronger lagrangean bounds
• Lagrangean relaxation. (With comments and rejoinder).
• Linear programming for the \(0-1\) quadratic knapsack problem
• Location, scheduling, design and integer programming
• Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods
• Reoptimization in Lagrangian methods for the 0-1 quadratic knapsack problem
• Surrogate gradient algorithm for Lagrangian relaxation

Cited in

(4)

• Lagrangean decomposition: A model yielding stronger lagrangean bounds
• Polynomial-size formulations and relaxations for the quadratic multiple knapsack problem
• Dynamic Lagrangian dual and reduced RLT constructs for solving \(0-1\) mixed-integer programs
• Concise RLT forms of binary programs: a computational study of the quadratic knapsack problem

Describes a project that uses

Uses Software

• Knapsack

This page was built for publication: Strong RLT1 bounds from decomposable Lagrangean relaxation for some quadratic \(0-1\) optimization problems with linear constraints

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