On the complexity of the surrogate dual of 0–1 programming

DOI10.1007/BF01919175zbMath0594.90061MaRDI QIDQ3725870

Endre Boros

Publication date: 1986

Published in: Zeitschrift für Operations Research (Search for Journal in Brave)

zbMATH Keywords

ellipsoid algorithmComputational resultssurrogate constraintssurrogate dual of a binary linear program

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Boolean programming (90C09)

Related Items (2)

On the complexity of surrogate and group relaxation for integer linear programs ⋮ Revisiting surrogate relaxation for the multidimensional knapsack problem

Cites Work

• The ellipsoid method and its consequences in combinatorial optimization
• Some relationships between lagrangian and surrogate duality in integer programming
• Technical Note—Searchability of the Composite and Multiple Surrogate Dual Functions
• Calculating surrogate constraints
• Feature Article—The Ellipsoid Method: A Survey
• Surrogate Constraint Duality in Mathematical Programming
• Discrete Programming by the Filter Method
• A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem
• Surrogate Constraints
• An Improved Implicit Enumeration Approach for Integer Programming
• Surrogate Mathematical Programming

This page was built for publication: On the complexity of the surrogate dual of 0–1 programming