An Additive Bounding Procedure for Combinatorial Optimization Problems

DOI10.1287/OPRE.37.2.319zbMath0676.90049OpenAlexW1982444996MaRDI QIDQ3832317

Matteo Fischetti, Paolo Toth

Publication date: 1989

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

Full work available at URL: https://doi.org/10.1287/opre.37.2.319

zbMATH Keywords

traveling salesmanbranch-and-boundlower boundsprecedence constraintslinear objective function

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Integer programming (90C10) Combinatorial optimization (90C27)

Related Items (37)

A branch-and-bound approach for spare unit allocation in a series system ⋮ A capacitated general routing problem on mixed networks ⋮ Static pickup and delivery problems: a classification scheme and survey. (With comments and rejoinder) ⋮ Exact and approximation algorithms for makespan minimization on unrelated parallel machines ⋮ An exact algorithm for the capacitated shortest spanning arborescence ⋮ Exact makespan minimization of unrelated parallel machines ⋮ A branch‐and‐bound algorithm for the double travelling salesman problem with two stacks ⋮ A bound for the symmetric travelling salesman problem through matroid formulation ⋮ Matheuristics: survey and synthesis ⋮ Column elimination for capacitated vehicle routing problems ⋮ An Additive Branch-and-Bound Algorithm for the Pickup and Delivery Traveling Salesman Problem with LIFO or FIFO Loading ⋮ The tree representation for the pickup and delivery traveling salesman problem with LIFO loading ⋮ CP-Based Local Branching ⋮ Recent advances in vehicle routing exact algorithms ⋮ Mobility allowance shuttle transit (MAST) services: MIP formulation and strengthening with logic constraints ⋮ A Stochastic Integer Programming Approach to Air Traffic Scheduling and Operations ⋮ Improved filtering for weighted circuit constraints ⋮ An additive bounding procedure for the asymmetric travelling salesman problem ⋮ An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts ⋮ Recent Models and Algorithms for One-to-One Pickup and Delivery Problems ⋮ A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems ⋮ Bounding, filtering and diversification in CP-based local branching ⋮ Hybrid optimization methods for time-dependent sequencing problems ⋮ On symmetric subtour problems ⋮ Models, relaxations and exact approaches for the capacitated vehicle routing problem ⋮ Exact algorithms for routing problems under vehicle capacity constraints ⋮ Driver scheduling based on “driver-friendly” vehicle schedules ⋮ The pickup and delivery traveling salesman problem with first-in-first-out loading ⋮ A new VRPPD model and a hybrid heuristic solution approach for e-tailing ⋮ Cluster based branching for the asymmetric traveling salesman problem ⋮ Computing lower bounds by destructive improvement: An application to resource-constrained project scheduling ⋮ An MDD-Based Lagrangian Approach to the Multicommodity Pickup-and-Delivery TSP ⋮ A heuristic algorithm for the asymmetric capacitated vehicle routing problem ⋮ New lower bounds for the symmetric travelling salesman problem ⋮ Exact Multiple Sequence Alignment by Synchronized Decision Diagrams ⋮ Minimum directed 1-subtree relaxation for score orienteering problem ⋮ An efficient genetic algorithm for the traveling salesman problem with precedence constraints

This page was built for publication: An Additive Bounding Procedure for Combinatorial Optimization Problems