Several branch-and-bound algorithms for the exact solution of the asymmetric traveling salesman problem (ATSP), based on the assignment problem (AP) relaxation, have been proposed in the literature. These algorithms perform very well for some instances (e.g., those with uniformly random integer...

Given n items, each having a weight w_i, and a container of capacity W, the Subset-Sum Problem (SSP) is to select a subset of the items whose total weight is closest to, without exceeding, W. The paper presents a mixed approach (depth first search-dynamic programming) to the exact solution of the...

We consider the NP-hard Multiple Depot Vehicle Scheduling Problem, in which a given set of time-tabled trips have to be assigned to vehicles stationed at different depots, so as to minimize the number of vehicles used and the overall operational cost. The problem arises in the management of...

Crew and vehicle scheduling are fundamental issues in public transit management. Informally, they can be described as the problem of determining the optimal duties for a set of crews (e.g., bus drivers) or vehicles (e.g., buses) so as to cover a given set of timetabled trips, satisfying a number...

Many algorithms have been developed for the optimal solution of the asymmetric travelling salesman problem: the most efficient ones are based on the subtour elimination approach. This paper presents a breadth-first branch and bound algorithm which differs from the method of Smith, Srinivasan and...

We present a new algorithm for the optimal solution of the 0-1 Knapsack problem, which is particularly effective for large-size problems. The algorithm is based on determination of an appropriate small subset of items and the solution of the corresponding "core problem": from this we derive a...

Erratum to Carpaneto, Giorgio, Paolo Toth. 1980. Branching and bounding criteria for the asymmetric travelling salesman problem. Management Sci. 26 (7) 736--743.

Two new algorithms recently proved to outperform all previous methods for the exact solution of the 0-1 Knapsack Problem. This paper presents a combination of such approaches, where, in addition, valid inequalities are generated and surrogate relaxed, and a new initial core problem is adopted....