Best reduction of the quadratic semi-assignment problem
The quadratic semi-assignment problem is stated, that is a quadratic assignment problem simplification, in which one of the sets of unique assignment constraints is relaxed. For the quadratic problem a reduction is defined as a pair, which consists of a real constant and a quadratic function with nonnegative coefficients. This pair constitutes the reduction if the sum of the constant and function is equal to the original objective function of the problem for each feasible solution. The authors focus on the best reduction of a quadratic semi-assignment problem, what is a reduction with the greatest constant. They prove that the best reduction can be obtained by solving a linear program. The optimal value of the linear program objective function yields the constant of the best reduction and reduced costs associated with the optimal solution constitute the nonnegative coefficients of the quadratic function. NEWLINENEWLINENEWLINEIn the sequel of the paper, the authors prove that their best reduction is strictly better than some other reductions. In the same sequel, results of numerical experiments are reported, which show that employment of the best reduction in quadratic semi-assignment problem resolution can reduce the associated computational time several times.
- 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
- 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
- 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)
