Surrogate duality in a branch-and-bound procedure for integer programming

DOI10.1016/0377-2217(88)90176-2MaRDI QIDQ1099783zbMATH OpenOpenAlexFDO

Authors Sanjiv Sarin, Mark H. Karwan, Ronald L. Rardin

Publication date 1988

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(88)90176-2

zbMATH Keywords

branch-and-boundLagrangean search methodsmulticonstraint knapsack problemssurrogate dual multiplierssurrogate dual values

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10)

Recommendations

• scientific article; zbMATH DE number 4072712
• scientific article; zbMATH DE number 4039640
• Publication:4206317
• Exact algorithm for the surrogate dual of an integer programming problem: Subgradient method approach
• On the complexity of the surrogate dual of 0–1 programming

Cites work

• scientific article; zbMATH DE number 4072712 (Why is no real title available?)
• scientific article; zbMATH DE number 3557512 (Why is no real title available?)
• scientific article; zbMATH DE number 3614502 (Why is no real title available?)
• scientific article; zbMATH DE number 3435272 (Why is no real title available?)
• A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem
• An Additive Algorithm for Solving Linear Programs with Zero-One Variables
• An Improved Implicit Enumeration Approach for Integer Programming
• Calculating surrogate constraints
• Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality
• New Greedy-Like Heuristics for the Multidimensional 0-1 Knapsack Problem
• Some relationships between lagrangian and surrogate duality in integer programming
• Surrogate Constraint Duality in Mathematical Programming
• Surrogate Dual Multiplier Search Procedures in Integer Programming
• Surrogate Mathematical Programming
• Technical Note—An Implementation of Surrogate Constraint Duality
• The Lagrangian Relaxation Method for Solving Integer Programming Problems

Cited in

(14)

• A computational evaluation of two subgradient search methods
• On zero duality gap in surrogate constraint optimization: the case of rational-valued functions of constraints
• On generalized surrogate duality in mixed-integer nonlinear programming
• On the complexity of the surrogate dual of 0–1 programming
• scientific article; zbMATH DE number 4039640 (Why is no real title available?)
• Surrogate gradient algorithm for Lagrangian relaxation
• An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem
• scientific article; zbMATH DE number 4126606 (Why is no real title available?)
• A trust region method for the solution of the surrogate dual in integer programming
• A solution procedure for general knapsack problems with a few constraints
• scientific article; zbMATH DE number 4072712 (Why is no real title available?)
• Zero duality gap in surrogate constraint optimization: a concise review of models
• Zero duality gap in integer programming: \(P\)-norm surrogate constraint method
• Utilizing the surrogate dual bound in capacity planning with economies of scale

This page was built for publication: Surrogate duality in a branch-and-bound procedure for integer programming

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