Non delayed relax-and-cut algorithms

DOI10.1007/s10479-005-3977-1zbMath1091.90082MaRDI QIDQ817212

Abilio Lucena

Publication date: 7 March 2006

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-005-3977-1

zbMATH Keywords

Lagrangian relaxation; relax-and-cut; dual bound strengthening; valid constraints

Mathematics Subject Classification ID

90C10: Integer programming

90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut

Related Items

A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs, A non-delayed relax-and-cut algorithm for scheduling problems with parallel machines, due dates and sequence-dependent setup times, A relax-and-cut algorithm for the set partitioning problem, Exact algorithms for the vertex separator problem in graphs

Uses Software

• CPLEX
• XPRESS
• DIP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Edge exchanges in the degree-constrained minimum spanning tree problem
• The Steiner tree polytope and related polyhedra
• Tree polytope on 2-trees
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships
• The volume algorithm: Producing primal solutions with a subgradient method
• Lagrangean heuristics for location problems
• Stronger \(K\)-tree relaxations for the vehicle routing problem
• Lagrangean relaxation. (With comments and rejoinder).
• Dynamic bundle methods
• Decomposition and dynamic cut generation in integer linear programming
• A Hybrid GRASP with Perturbations for the Steiner Problem in Graphs
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut
• On finding steiner vertices
• Steiner problem in networks: A survey
• A new approach to the maximum-flow problem
• An SST-based algorithm for the steiner problem in graphs
• A restricted Lagrangean approach to the traveling salesman problem
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
• EXACT SOLUTIONS OF RECTANGULAR PARTITIONS VIA INTEGER PROGRAMMING
• Validation of subgradient optimization
• Optimal rectangular partitions
• Matroids and the greedy algorithm
• Integer Programming and Combinatorial Optimization
• A Lagrangian relaxation approach to the edge-weighted clique problem
• Steiner tree problems