Best reduction of the quadratic semi-assignment problem

DOI10.1016/S0166-218X(00)00257-2MaRDI QIDQ5931788zbMATH OpenOpenAlexFDO

Authors Alain Billionnet, Sourour Elloumi

Publication date 17 June 2002

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0166-218x(00)00257-2

zbMATH Keywords

0-1 quadratic programmingdualitylinear programmingreductionsemi-assignment problem

Mathematics Subject Classification ID

Linear programming (90C05) Boolean programming (90C09) Quadratic programming (90C20)

Recommendations

• Effective formulation reductions for the quadratic assignment problem
• Lower bounds for the quadratic semi-assignment problem
• scientific article; zbMATH DE number 3982880
• Two classes of quadratic assignment problems that are solvable as linear assignment problems
• Comparison of Quadratic Convex Reformulations to Solve the Quadratic Assignment Problem

Cites work

• A lower bound for a constrained quadratic \(0\)-\(1\) minimization problem
• A Selection Problem of Shared Fixed Costs and Network Flows
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• An efficient algorithm for a task allocation problem
• Computing Lower Bounds for the Quadratic Assignment Problem with an Interior Point Algorithm for Linear Programming
• scientific article; zbMATH DE number 714527 (Why is no real title available?)
• Location, scheduling, design and integer programming
• On the quadratic assignment problem
• Roof duality, complementation and persistency in quadratic 0–1 optimization
• Unconstrained 0-1 optimization and Lagrangean relaxation

Cited in

(13)

• An algorithm for the generalized quadratic assignment problem
• A study of the quadratic semi-assignment polytope
• Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
• The Boolean quadratic programming problem with generalized upper bound constraints
• Quadratic assignment problem variants: a survey and an effective parallel memetic iterated tabu search
• Fast r-flip move evaluations via closed-form formulae for Boolean quadratic programming problems with generalized upper bound constraints
• Comparison of Quadratic Convex Reformulations to Solve the Quadratic Assignment Problem
• Exact solution of emerging quadratic assignment problems
• An Exact Algorithm for the Quadratic Multiknapsack Problem with an Application to Event Seating
• Inductive linearization for binary quadratic programs with linear constraints
• Inductive linearization for binary quadratic programs with linear constraints: a computational study
• A survey for the quadratic assignment problem
• Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the reformulation-linearization technique

This page was built for publication: Best reduction of the quadratic semi-assignment problem

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