Surrogate duality in a branch-and-bound procedure for integer programming
The existence of efficient techniques such as subgradient search for solving Lagrangean duals has led to some very successful applications of Lagrangean duality in solving specially structured discrete problems. While surrogate duals have been theoretically shown to provide stronger bounds, the complexity of surrogate dual multiplier search has discouraged their employment in solving integer programs. We have recently suggested a new strategy for computing surrogate dual values that allows us to directly use established Lagrangean search methods for exploring surrogate dual multipliers. This paper considers the problem of incorporating surrogate duality within a branch-and-bound procedure for solving integer programming problems. Computational experience with randomly generated multiconstraint knapsack problems is also reported.
- 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
- 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?)
- 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
- A computational evaluation of two subgradient search methods
- Surrogate gradient algorithm for Lagrangian relaxation
- An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem
- Exact algorithm for the surrogate dual of an integer programming problem: Subgradient method approach
- Zero duality gap in integer programming: \(P\)-norm surrogate constraint method
- On the complexity of surrogate and group relaxation for integer linear programs
- On generalized surrogate duality in mixed-integer nonlinear programming
- Zero duality gap in surrogate constraint optimization: a concise review of models
- Utilizing the surrogate dual bound in capacity planning with economies of scale
- On the complexity of the surrogate dual of 0–1 programming
- scientific article; zbMATH DE number 4039640 (Why is no real title available?)
- scientific article; zbMATH DE number 4072712 (Why is no real title available?)
- scientific article; zbMATH DE number 4126606 (Why is no real title available?)
- On zero duality gap in surrogate constraint optimization: the case of rational-valued functions of constraints
- 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
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)
