Efficient cuts in Lagrangean `relax-and-cut' schemes

DOI10.1016/S0377-2217(97)00034-9zbMath0957.90091MaRDI QIDQ1291724

Monique Guignard

Publication date: 22 March 2001

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

zbMATH Keywords

integer programmingLagrangean relaxationcutting planesvalid inequalitiesfacetscutsduality gaps

Mathematics Subject Classification ID

Integer programming (90C10) Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Numerical methods involving duality (49M29)

Related Items

A New Lagrangian Based Branch and Bound Algorithm for the 0-1 Knapsack Problem, Lagrangean relaxation. (With comments and rejoinder)., A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships, A relax-and-cut framework for large-scale maximum weight connected subgraph problems, Dynamic Lagrangian dual and reduced RLT constructs for solving \(0-1\) mixed-integer programs, On the computational efficiency of subgradient methods: a case study with Lagrangian bounds, Solving linear programming relaxations associated with Lagrangean relaxations by Fenchel cutting planes, An homage to Joseph-Louis Lagrange and Pierre Huard, Decomposition and dynamic cut generation in integer linear programming, The unsuitable neighbourhood inequalities for the fixed cardinality stable set polytope, A non-delayed relax-and-cut algorithm for scheduling problems with parallel machines, due dates and sequence-dependent setup times, A Lagrangian relax-and-cut approach for the two-stage capacitated facility location problem, New approaches for optimizing over the semimetric polytope, Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut, Uncapacitated Euclidean hub location: strengthened formulation, new facets and a relax-and-cut algorithm, About Lagrangian methods in integer optimization

Uses Software

• GAMS

Cites Work

• A facet generation and relaxation technique applied to an assignment problem with side constraints
• A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships
• A Multiplier Adjustment Method for the Generalized Assignment Problem
• Technical Note—An Improved Dual Based Algorithm for the Generalized Assignment Problem
• Facets of the Asymmetric Traveling Salesman Polytope
• A branch and bound algorithm for the generalized assignment problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item