Some relationships between lagrangian and surrogate duality in integer programming

DOI10.1007/BF01588253zbMath0421.90056MaRDI QIDQ3854930

Ronald L. Rardin, Mark H. Karwan

Publication date: 1979

Published in: Mathematical Programming (Search for Journal in Brave)

zbMATH Keywords

Lagrangian relaxationlinear programming relaxationsurrogate relaxationsurrogate dualitysurrogate dualcapital budgetingsurrogate constraintintegrality propertyBenders' type algorithmempirical computations

Mathematics Subject Classification ID

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

Related Items (33)

On using approximations of the Benders master problem ⋮ On Generalized Surrogate Duality in Mixed-Integer Nonlinear Programming ⋮ A new Lagrangian relaxation approach to the generalized assignment problem ⋮ Surrogate duality in a branch-and-bound procedure for integer programming ⋮ On the complexity of the surrogate dual of 0–1 programming ⋮ Exact algorithm for the surrogate dual of an integer programming problem: Subgradient method approach ⋮ A trust region method for the solution of the surrogate dual in integer programming ⋮ Lagrangean decomposition: A model yielding stronger lagrangean bounds ⋮ A theoretical and empirical investigation on the Lagrangian capacities of the \(0\)-\(1\) multidimensional knapsack problem ⋮ The multidimensional 0-1 knapsack problem: an overview. ⋮ The design of multiactivity multifacility systems ⋮ A survey on the continuous nonlinear resource allocation problem ⋮ A relax-and-cut algorithm for the set partitioning problem ⋮ Searching for optimal integer solutions to set partitioning problems using column generation ⋮ An application of a Lagrangian-type relaxation for the uncapacitated facility location problem ⋮ Solving network design problems via iterative aggregation ⋮ Zero duality gap in integer programming: \(P\)-norm surrogate constraint method ⋮ Lagrangean/surrogate relaxation for generalized assignment problems ⋮ On duality for Boolean programming ⋮ Future paths for integer programming and links to artificial intelligence ⋮ Development of a new approach for deterministic supply chain network design ⋮ Relaxation heuristics for a generalized assignment problem ⋮ Calculating surrogate constraints ⋮ A comparison of Lagrangean and surrogate relaxations for the maximal covering location problem ⋮ Johri's general dual, the Lagrangian dual, and the surrogate dual ⋮ Algorithms for large scale set covering problems ⋮ Zero-one integer programs with few contraints - lower bounding theory ⋮ Multicriteria integer programming: A (hybrid) dynamic programming recursive approach ⋮ Using logical surrogate information in Lagrangean relaxation: An application to symmetric traveling salesman problems ⋮ Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality ⋮ Dual-based heuristics for a hierarchical covering location problem ⋮ On generalized surrogate duality in mixed-integer nonlinear programming ⋮ The multidimensional 0-1 knapsack problem -- bounds and computational aspects

Cites Work

• Unnamed Item
• Unnamed Item
• A survey of various tactics for generating Lagrangian multipliers in the context of Lagrangian duality
• Surrogate Dual Multiplier Search Procedures in Integer Programming
• Optimal Solution of Scheduling Problems Using Lagrange Multipliers: Part I
• Surrogate Constraint Duality in Mathematical Programming
• The Traveling-Salesman Problem and Minimum Spanning Trees
• Surrogate Mathematical Programming
• The Generalized Penalty-Function/Surrogate Model
• Technical Note—Bounding Nonconvex Programs by Conjugates

This page was built for publication: Some relationships between lagrangian and surrogate duality in integer programming