Dual formulations and subgradient optimization strategies for linear programming relaxations of mixed-integer programs

DOI10.1016/0166-218X(88)90041-8zbMath0656.90070MaRDI QIDQ1110459

Hanif D. Sherali, Danny C. Myers

Publication date: 1988

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

relaxationcomputational experiencesubgradient optimizationLagrangian dualmixed integer linear programsadditional redundant constraintsdual feasible solutionset covering constraints

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Mixed integer programming (90C11) Linear programming (90C05) Boolean programming (90C09)

Related Items

Convergence and computational analyses for some variable target value and subgradient deflection methods, A trust region target value method for optimizing nondifferentiable Lagrangian duals of linear programs, A primal-dual conjugate subgradient algorithm for specially structured linear and convex programming problems, A Langrangean heuristic for the \(p_ k\)-median dynamic location problem, RLT: A unified approach for discrete and continuous nonconvex optimization, On using exterior penalty approaches for solving linear programming problems, Design of a distribution network using primal-dual decomposition, Lagrangian heuristics for the two-echelon, single-source, capacitated facility location problem, Lagrangean Relaxation-Based Techniques for Solving Facility Location Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the choice of step size in subgradient optimization
• A survey of various tactics for generating Lagrangian multipliers in the context of Lagrangian duality
• An aggregate subgradient method for nonsmooth convex minimization
• Surrogate Dual Multiplier Search Procedures in Integer Programming
• Solving Large-Scale Zero-One Linear Programming Problems
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• `` Direct Search Solution of Numerical and Statistical Problems
• A Dual-Based Procedure for Uncapacitated Facility Location
• Technical Note—Surrogate Constraints and the Strength of Bounds Derived from 0-1 Benders' Partitioning Procedures
• Validation of subgradient optimization
• The Traveling-Salesman Problem and Minimum Spanning Trees
• Minimization of unsmooth functionals
• The traveling-salesman problem and minimum spanning trees: Part II