An Additive Bounding Procedure for Combinatorial Optimization Problems

Matteo Fischetti and Paolo Toth
Additional contact information
Matteo Fischetti: University of Bologna, Bologna, Italy
Paolo Toth: University of Bologna, Bologna, Italy

Operations Research, 1989, vol. 37, issue 2, 319-328

Abstract: We know that the effectiveness of the branch-and-bound algorithms proposed for the solution of combinatorial optimization problems greatly depends on the tightness of the available bounds. In this paper, we consider optimization problems with a linear objective function. We propose an additive approach for computing lower bounds that yields an increasing sequence of values. An application to the traveling salesman problem with precedence constraints is presented to exemplify the technique.

Keywords: networks/graphs: traveling salesman problem; programming; integer algorithms: bounding procedures for branch-and-bound algorithms (search for similar items in EconPapers)
Date: 1989
References: Add references at CitEc
Citations: View citations in EconPapers (22)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.37.2.319 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:37:y:1989:i:2:p:319-328

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().