The robust shortest path problem in series-parallel multidigraphs with interval data

In this paper the robust shortest path problem in edge series-parallel multidigraphs with interval costs is examined. The maximal regret criterion is applied to calculate the optimal solution. It is shown that this problem is NP-hard. A pseudopolynomial algorithm for the studied problem is constructed.     

The robust shortest path problem with interval data via Benders decomposition

Many real problems can be modelled as robust shortest path problems on digraphs with interval costs, where intervals represent uncertainty about real costs and a robust path is not too far from the shortest path for each possible configuration of the arc costs. In this paper we discuss the application of a Benders decomposition approach to this problem. Computational results confirm the efficiency of the new algorithm. It is able to clearly outperform state-of-the-art algorithms on many classes of networks. For the remaining classes we identify the most promising algorithm among the others, depending of the characteristics of the networks. Received: September 2004 / Accepted: March 2005 AMS classification: 90C47, 52B05, 90C57 The work was partially supported by the European Commission IST projects MOSCA (IST-2000-29557) and BISON (IST-2001-38923). All correspondence to: Roberto Montemanni     

A branch and bound algorithm for the maximum diversity problem

This article begins with a review of previously proposed integer formulations for the maximum diversity problem (MDP). This problem consists of selecting a subset of elements from a larger set in such a way that the sum of the distances between the chosen elements is maximized. We propose a branch and bound algorithm and develop several upper bounds on the objective function values of partial solutions to the MDP. Empirical results with a collection of previously reported instances indicate that the proposed algorithm is able to solve all the medium-sized instances (with 50 elements) as well as some large-sized instances (with 100 elements). We compare our method with the best previous linear integer formulation solved with the well-known software Cplex. The comparison favors the proposed procedure.     

On the complexity of the robust spanning tree problem with interval data

This paper studies the complexity of the robust spanning tree problem with interval data (RSTID). It shows that the problem is NP-complete, settling the conjecture of Kouvelis and Yu, and that it remains so for complete graphs or when the intervals are all [0,1]. These results indicate that the difficulty of RSTID stems from both the graph topology and the structure of the cost intervals, suggesting new directions for search algorithms.     

A new branch and bound algorithm for cell formation problem

Cell formation (CF) is the first and the most important problem in designing cellular manufacturing systems. Due to its non-polynomial nature, various heuristic and metaheuristic algorithms have been proposed to solve CF problem. Despite the popularity of heuristic algorithms, few studies have attempted to develop exact algorithms, such as branch and bound (B&B) algorithms, for this problem. We develop three types of branch and bound algorithms to deal with the cell formation problem. The first algorithm uses a binary branching scheme based on the definitions provided for the decision variables. Unlike the first algorithm, which relies on the mathematical model, the second one is designed based on the structure of the cell formation problem. The last algorithm has a similar structure to the second one, except that it has the ability to eliminate duplicated nodes in branching trees. The proposed branch and bound algorithms and a hybrid genetic algorithm are compared through some numerical examples. The results demonstrate the effectiveness of the modified problem-oriented branch and bound algorithm in solving relatively large size cell formation problems.     

A simplicial branch and bound duality-bounds algorithm for the linear sum-of-ratios problem

In this article, we present and validate a simplicial branch and bound duality-bounds algorithm for globally solving the linear sum-of-ratios fractional program. The algorithm computes the lower bounds called for during the branch and bound search by solving ordinary linear programming problems. These problems are derived by using Lagrangian duality theory. The algorithm applies to a wide class of linear sum-of-ratios fractional programs. Two sample problems are solved, and the potential practical and computational advantages of the algorithm are indicated.     

Distributionally robust stochastic shortest path problem

This paper considers a stochastic version of the shortest path problem, the Distributionally Robust Stochastic Shortest Path Problem(DRSSPP) on directed graphs. In this model, the arc costs are deterministic, while each arc has a random delay. The mean vector and the second-moment matrix of the uncertain data are assumed known, but the exact information of the distribution is unknown. A penalty occurs when the given delay constraint is not satisfied. The objective is to minimize the sum of the path cost and the expected path delay penalty. As it is NP-hard, we approximate the DRSSPP with a semidefinite programming (SDP for short) problem, which is solvable in polynomial time and provides tight lower bounds.     

A best-first branch and bound algorithm for unconstrained two-dimensional cutting problems

This paper is concerned with the problem of unconstrained two-dimensional cutting of small rectangular pieces, each of which has its own profit and size, from a large rectangular plate so as to maximize the profit-sum of the pieces produced. Hifi and Zissimopoulos's recursive algorithm using G and Kang's upper bound is presently the most efficient exact algorithm for the problem. We propose a best-first branch and bound algorithm based upon the bottom-up approach that is more efficient than their recursive algorithm. The proposed algorithm uses efficient upper bound and branching strategies that can reduce the number of nodes that must be searched significantly. We demonstrate the efficiency of the proposed algorithm through computational experiments.     

A branch and bound algorithm for the matrix bandwidth minimization

In this article, we first review previous exact approaches as well as theoretical contributions for the problem of reducing the bandwidth of a matrix. This problem consists of finding a permutation of the rows and columns of a given matrix which keeps the non-zero elements in a band that is as close as possible to the main diagonal. This NP-complete problem can also be formulated as a labeling of vertices on a graph, where edges are the non-zero elements of the corresponding symmetrical matrix. We propose a new branch and bound algorithm and new expressions for known lower bounds for this problem. Empirical results with a collection of previously reported instances indicate that the proposed algorithm compares favourably to previous methods.     

Some tractable instances of interval data minmax regret problems

In this paper, we provide polynomial and pseudopolynomial algorithms for classes of particular instances of interval data minmax regret graph problems. These classes are defined using a parameter that measures the distance from well-known solvable instances. Tractable cases occur when the parameter is bounded by a constant.     

A branch and bound algorithm for the robust spanning tree problem with interval data

The robust spanning tree problem is a variation, motivated by telecommunications applications, of the classic minimum spanning tree problem. In the robust spanning tree problem edge costs lie in an interval instead of having a fixed value.Interval numbers model uncertainty about the exact cost values. A robust spanning tree is a spanning tree whose total cost minimizes the maximum deviation from the optimal spanning tree over all realizations of the edge costs. This robustness concept is formalized in mathematical terms and is used to drive optimization.In this paper a branch and bound algorithm for the robust spanning tree problem is proposed. The method embeds the extension of some results previously presented in the literature and some new elements, such as a new lower bound and some new reduction rules, all based on the exploitation of some peculiarities of the branching strategy adopted.Computational results obtained by the algorithm are presented. The technique we propose is up to 210 faster than methods recently appeared in the literature.     

Labeling algorithm for the shortest path problem with turn prohibitions with application to large-scale road networks

In real road networks, the presence of no-left, no-right or no U-turn signs, restricts the movement of vehicles at intersections. These turn prohibitions must be considered when calculating the shortest path between a starting and an ending point in a road network. We propose an extension of Dijkstra’s algorithm to solve the shortest path problem with turn prohibitions. The method uses arc labeling and a network structure with low memory requirements. We compare the proposed method with the dual graph approach in a set of randomly generated networks and Bogotá’s large-scale road network. Our computational experiments show that the performance of the proposed method is better than that of the dual graph approach, both in terms of computing time and memory requirements. We co-developed a Web-based decision support system for computing shortest paths with turn prohibitions that uses the proposed method as the core engine.     

A branch and bound algorithm for determining locations of long-term care facilities

This paper focuses on the problem of determining locations for long-term care facilities with the objective of balancing the numbers of patients assigned to the facilities. We present a branch and bound algorithm by developing dominance properties, a lower bounding scheme and a heuristic algorithm for obtaining an upper bound for the problem. For evaluation of the suggested branch and bound algorithm, computational experiments are performed on a number of test problems. Results of the experiments show that the suggested algorithm gives optimal solutions of problems of practical sizes in a reasonable amount of computation time.     

Proportion-based robust optimization and team orienteering problem with interval data

In this paper, a proportion-based robust optimization approach is developed to deal with uncertain combinatorial optimization problems. This approach assumes that a certain proportion of uncertain coefficients in each solution are allowed to change and optimizes a deterministic model so as to achieve a trade-off between optimality and feasibility when the coefficients change. We apply this approach on team orienteering problem with interval data (TOPID), a variant of vehicle routing problem, which has not yet been studied before. A branch and price algorithm is proposed to solve the robust counterpart by using two novel dominance relations. Finally, numerical study is performed. The results show the usefulness of the proposed robust optimization approach and the effectiveness of our algorithm.     

A branch and bound algorithm for the maximum clique problem

We present a branch and bound algorithm for the maximum clique problem in arbitrary graphs. The main part of the algorithm consists in the determination of upper bounds by graph colorings. Using a modification of a known graph coloring method called DSATUR we simultaneously derive lower and upper bounds for the clique number.

---

Zusammenfassung Wir stellen einen Branch and Bound Algorithmus für das Maximum Clique Problem in einem beliebigen Graphen vor. Das Hauptaugenmerk richtet sich dabei auf die Bestimmung oberer Schranken mit Hilfe von Färbungen von Graphen. Es wird eine Modifikation einer bekannten Färbungsmethode, genannt DSATUR, verwendet, mit der sich gleichzeitig obere und untere Schranken für die Cliquezahl erstellen lassen.

     

A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags

We consider the one-machine scheduling problem with minimum and maximum time lags while minimizing the makespan. This problem typically arises in a manufacturing environment where the next job has to be carried out within a specific time range after the completion of the immediately preceding job. We describe a branch and bound algorithm, based on the input and output of a clique and the relevant propositions, for finding the optimal waiting times. The computational experiments give promising results, showing whether a given instance is feasible or infeasible. With the proposed branch and bound algorithm we can either find an optimal schedule or establish the infeasibility within an acceptable run time.     

Solving the shortest path tour problem

In this paper, we study the shortest path tour problem in which a shortest path from a given origin node to a given destination node must be found in a directed graph with non-negative arc lengths. Such path needs to cross a sequence of node subsets that are given in a fixed order. The subsets are disjoint and may be different-sized. A polynomial-time reduction of the problem to a classical shortest path problem over a modified digraph is described and two solution methods based on the above reduction and dynamic programming, respectively, are proposed and compared with the state-of-the-art solving procedure. The proposed methods are tested on existing datasets for this problem and on a large class of new benchmark instances. The computational experience shows that both the proposed methods exhibit a consistent improved performance in terms of computational time with respect to the existing solution method.     

New efficient shortest path simplex algorithm: pseudo permanent labels instead of permanent labels

We introduce a new network simplex pivot rule for the shortest path simplex algorithm. This new pivot rule chooses a subset of non-basic arcs to simultaneously enter into the basis. We call this operation a multiple pivot. We show that a shortest path simplex algorithm with this pivot rule performs O(n) multiple pivots and runs in O(nm) time. Our pivot rule is based on the new concept of a pseudo permanently labeled node, and it can be adapted to design a new label-correcting algorithm that runs in O(nm). Moreover, this concept lets us introduce new rules to identify negative cycles. Finally, we compare the network simplex algorithm with multiple pivots with other previously proposed efficient network simplex algorithm in a computational experiment.     

A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations

A hybrid flow shop scheduling problem (HFSP) with assembly operations is studied in this paper. In the considered problem, a number of products of the same kind are produced. Each product is assembled using a set of several parts. At first, the parts are produced in a hybrid flow shop and then they are assembled in an assembly stage to produce products. The considered objective is to minimize the completion time of all products (makespan). This problem has been proved strongly NP-hard, so in order to solve it, a hierarchical branch and bound algorithm is presented. Also, some lower and upper bounds are developed to increase the efficiency of the proposed algorithm. The numerical experiments are used to evaluate the performance of the proposed algorithm.     

A branch and bound network approach to the canonical constrained entropy problem

In this paper, we present a branch and bound algorithm for solving the constrained entropy mathematical programming problem. Unlike other methods for solving this problem, our method solves more general problems with inequality constraints. The advantage of the proposed technique is that the relaxed problem solved at each node is a singly constrained network problem. The disadvantage is that the relaxed problem has twice as many variables as the original problem. An application to regional planning is given, and an example problem is solved.