A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships

DOI10.1007/BF02085641zbMath0833.90068OpenAlexW2015411837MaRDI QIDQ1339126

Kavindra Malik, Monique Guignard, Laureano Fernando Escudero Bueno

Publication date: 15 February 1996

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

Full work available at URL: https://doi.org/10.1007/bf02085641

zbMATH Keywords

makespandirected graphprecedence relationsequential ordering problemLagrangian relax-and-cut approachminimum weight Hamilton pathstrong lower bounds

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic scheduling theory in operations research (90B35)

Related Items (29)

Lagrangean relaxation. (With comments and rejoinder). ⋮ A sequential ordering problem in automotive paint shops ⋮ New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints ⋮ Constrained shortest path tour problem: branch-and-price algorithm ⋮ Stronger multi-commodity flow formulations of the (capacitated) sequential ordering problem ⋮ Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs ⋮ Two-phase branch and bound algorithm for robotic cells rescheduling considering limited disturbance ⋮ An improved ant colony system for the sequential ordering problem ⋮ A relax-and-cut framework for large-scale maximum weight connected subgraph problems ⋮ Dynamic bundle methods ⋮ On due-date based valid cuts for the sequential ordering problem ⋮ Coupling ant colony systems with strong local searches ⋮ Dynamic Lagrangian dual and reduced RLT constructs for solving \(0-1\) mixed-integer programs ⋮ A hybrid particle swarm optimization approach for the sequential ordering problem ⋮ A branch-and-bound algorithm for the precedence-constrained minimum-cost arborescence problem ⋮ A heuristic manipulation technique for the sequential ordering problem ⋮ A relax-and-cut algorithm for the set partitioning problem ⋮ Branch-and-bound for the precedence constrained generalized traveling salesman problem ⋮ New cutting-planes for the time- and/or precedence-constrained ATSP and directed VRP ⋮ An homage to Joseph-Louis Lagrange and Pierre Huard ⋮ A relax-and-cut framework for Gomory mixed-integer cuts ⋮ A Lagrangian heuristic algorithm for a real-world train timetabling problem ⋮ Lagrangian heuristics for the quadratic knapsack problem ⋮ Stronger \(K\)-tree relaxations for the vehicle routing problem ⋮ Computational analysis of a flexible assembly system design problem ⋮ Efficient cuts in Lagrangean `relax-and-cut' schemes ⋮ A non-delayed relax-and-cut algorithm for scheduling problems with parallel machines, due dates and sequence-dependent setup times ⋮ Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut ⋮ Non delayed relax-and-cut algorithms

Cites Work

• A facet generation and relaxation technique applied to an assignment problem with side constraints
• A production planning problem in FMS
• An inexact algorithm for the sequential ordering problem
• Efficient cuts in Lagrangean `relax-and-cut' schemes
• Thek best spanning arborescences of a network
• Finding optimum branchings
• Validation of subgradient optimization
• Optimum branchings

This page was built for publication: A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships