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.
Additive bounding procedure for combinatorial optimization problems
Fischetti Matteo;
1989
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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
