Beam search heuristic to solve stochastic integer problems under probabilistic constraints

This paper proposes a Beam Search heuristic strategy to solve stochastic integer programming problems under probabilistic constraints. Beam Search is an adaptation of the classical Branch and Bound method in which at any level of the search tree only the most promising nodes are kept for further exploration, whereas the remaining are pruned out permanently. The proposed algorithm has been compared with the Branch and Bound method. The numerical results collected on the probabilistic set covering problem show that the Beam Search technique is very efficient and appears to be a promising tool to solve difficult stochastic integer problems under probabilistic constraints.     

Shortest path problem with forbidden paths: The elementary version

This paper addresses the elementary shortest path problem with forbidden paths. The main aim is to find the shortest paths from a single origin node to every other node of a directed graph, such that the solution does not contain any path belonging to a given set (i.e., the forbidden set). It is imposed that no cycle can be included in the solution. The problem at hand is formulated as a particular instance of the shortest path problem with resource constraints and two different solution approaches are defined and implemented. One is a Branch & Bound based algorithm, the other is a dynamic programming approach. Different versions of the proposed solution strategies are developed and tested on a large set of test problems.     

An exact approach for solving integer problems under probabilistic constraints with random technology matrix

This paper addresses integer programming problems under probabilistic constraints involving discrete distributions. Such problems can be reformulated as large scale integer problems with knapsack constraints. For their solution we propose a specialized Branch and Bound approach where the feasible solutions of the knapsack constraint are used as partitioning rules of the feasible domain. The numerical experience carried out on a set covering problem with random covering matrix shows the validity of the solution approach and the efficiency of the implemented algorithm.     

An approach for solving a class of transportation scheduling problems

An algorithm is developed for solving a class of transportation scheduling problems. It applies for a variety of problems such as: the Combining Truck Trip problem, the Delivery problem, the School Bus problem, the Assignment of Buses to Schedules, and the Travelling Salesman problem. The objective functions of the above problems differ from each other. Yet, by using the “savings method” proposed by Clarke and Wright, and extended by Gaskell, we are able to define each one of the above problems as a series of assignment problems. The cost matrix entries of each one of the assignment problems are a function of the constraints of the particular routing or scheduling problem. The solution to the assignment problem determines an upper bound of the optimal solution to the original problem. By combining the above procedure with a Branch and Bound procedure, it is possible to obtain the optimal solution in a finite number of steps. In some cases the Branch and Bound process can be eliminated due to the nature of the problem and in those cases the algorithm is efficient.     

Are Branch and Bound and A* Algorithms Identical?

Heuristic Search and Branch and Bound algorithms have many similarities. In this paper, we address the question of the extent to which they are similar. We firstly show that these algorithms apply the same principles, although generating graphs with different properties: Heuristic Search can explore any kind of graphs, whereas the Branch and Bound algorithm generates particular graphs with a restrictive inheritance property. Nevertheless, we show that the Branch and Bound principles can be used to perform Heuristic Search. We conclude that the two types of algorithms are therefore essentially identical; they only differ at the interpretation level.     

Some branch and bound techniques for nonlinear optimization

The range of nonlinear optimization problems which can be solved by Linear Programming and the Branch and Bound algorithm is extended by introducing Chains of Linked Ordered Sets and by allowing automatic interpolation of new variables. However this approach involves solving a succession of linear subproblems, whose solutions in general violate the logical requirements of the nonlinear formulation and may lie far from any local or global optimum. The paper describes techniques which are designed to improve the performance of the Branch and Bound algorithm on problems containing chains, and which also yield benefits in integer programming.Each linear subproblem is tightened towards the corresponding nonlinear problem by removing variables which must logically be nonbasic in any feasible solution. This is achieved by a presolve procedure, and also by post-optimal Lagrangian relaxation which tightens the bound on the objective function by assessing the cheapest way to satisfy any violated chain constraints. Frequently fewer subsequent branches are required to find a feasible solution or to prove infeasibility.Formerly of Scicon Ltd.     

A continuous DC programming approach to the strategic supply chain design problem from qualified partner set

We present a new continuous approach based on the DC (difference of convex functions) programming and DC algorithms (DCA) to the problem of supply chain design at the strategic level when production of a new market opportunity has to be launched among a set of qualified partners. A well known formulation of this problem is the mixed integer linear program. In this paper, we reformulate this problem as a DC program by using an exact penalty technique. The proposed algorithm is a combination of DCA and Branch and Bound scheme. It works in a continuous domain but provides mixed integer solutions. Numerical simulations on many empirical data sets show the efficiency of our approach with respect to the standard Branch and Bound algorithm.     

Research in the Limiting Efficiency of Plastic Deformation of Multilayer Tension (Compression) Bars

A method is proposed for calculating the limiting loads of multilayer bars in plastic deformation. The regularities of changes in the efficiency factor (EF) of plastic deformation in relation to the elastic moduli of the materials of which the bars are composed, the stress which causes the material plasticity, and variations in the cross-sectional areas of layers are examined. Mathematical expressions are derived which allow one to easily calculate the EF for arbitrary values of variable parameters and to find the limiting values of EF when one of the parameters is changed. The equivalent tension diagram for a multilayer bar is obtained in relation to the strength and stiffness of materials and their number and cross-sectional areas.     

Two-stage workforce planning under demand fluctuations and uncertainty

We address a multi-category workforce planning problem for functional areas located at different service centres, each having office-space and recruitment capacity constraints, and facing fluctuating and uncertain workforce demand. A deterministic model is initially developed to deal with workforce fluctuations based on an expected demand profile over the horizon. To hedge against the demand uncertainty, we also propose a two-stage stochastic program, in which the first stage makes personnel recruiting and allocation decisions, while the second stage reassigns workforce demand among all units. A Benders’ decomposition-based algorithm is designed to solve this two-stage stochastic mixed-integer program. Computational results based on some practical numerical experiments are presented to provide insights on applying the deterministic versus the stochastic programming approach, and to demonstrate the efficacy of the proposed algorithm as compared with directly solving the model using its deterministic equivalent.     

Cost optimal allocation of rail passenger lines

We consider the problem of cost optimal railway line allocation for passenger trains for the Dutch railway system. At present, the allocation of passenger lines by Dutch Railways is based on maximizing the number of direct travelers. This paper develops an alternative approach that takes operating costs into account. A mathematical programming model is developed which minimizes the operating costs subject to service constraints and capacity requirements. The model optimizes on lines, line types, routes, frequencies and train lengths. First, the line allocation model is formulated as an integer nonlinear programming model. This model is transformed into an integer linear programming model with binary decision variables. An algorithm is presented which solves the problem to optimality. The algorithm is based upon constraint satisfaction and a Branch and Bound procedure. The algorithm is applied to a subnetwork of the Dutch railway system for which it shows a substantial cost reduction. Further application and extension seem promising.     

Ein LIFO Branch and Bound Verfahren zur optimalen Altstoffbehälterallokation

Zusammenfassung In diesem Artikel wird auf ein Problem eingegangen, das sich im Rahmen einer abfallwirtschaftlichen Studie ergab, in der die Durchführbarkeit von Altstoffsammlungen im dichtverbauten Siedlungsgebiet untersucht wurde. Als wichtige Teilaufgabe war dabei eine platzminimale Altstoffbehälterkombination für jede Altstoffart und für jedes Haus des untersuchten Sammelgebietes zu ermitteln, wobei unter anderem die Zugänglichkeit des Behälterraumes für die Sammelmannschaft und dessen topographische Gegebenheiten zu beachten waren. Zur Lösung dieser Aufgabe, deren Formalisierung auf ein ganzzahliges LP führte, wurde ein LIFO Branch and Bound Verfahren entwickelt. Dieses wird an Hand der wesentlichen Bestandteile eines jeden Algorithmus vom Branch and Bound Typ: der Branching Strategie, der Bounding Strategie und der Search Strategie dargestellt. Der Algorithmus wurde in PL/I programmiert und hat seine Leistungsfähigkeit in zahlreichen Programmläufen unter Beweis gestellt.

---

Summary In this article a problem is treated which rose in the course of a research into the suitability for reconditioning used materials. This study analyzes the feasibility of scrap collection in densily populated, urban areas. One major aspect was to provide for a space saving combination of containers for every kind of scrap and for each house of the test area, bearing in mind the constraints given by the topographical conditions of the container room and its accessibility to the collection personnel. The formulation of this problem led to an all integer program. To solve this program a LIFO branch and bound algorithm was developed. The algorithm is presented by discussing its branching strategy, its bounding strategy and its search strategy, which constitute the essential parts of each procedure of the branch and bound type. The algorithm was programmed in PL/I and proved its efficiency in numerous runs.

     

Cutting plane algorithms for solving a stochastic edge-partition problem

We consider the edge-partition problem, which is a graph theoretic problem arising in the design of Synchronous Optical Networks. The deterministic edge-partition problem considers an undirected graph with weighted edges, and simultaneously assigns nodes and edges to subgraphs such that each edge appears in exactly one subgraph, and such that no edge is assigned to a subgraph unless both of its incident nodes are also assigned to that subgraph. Additionally, there are limitations on the number of nodes and on the sum of edge weights that can be assigned to each subgraph. In this paper, we consider a stochastic version of the edge-partition problem in which we assign nodes to subgraphs in a first stage, realize a set of edge weights from a finite set of alternatives, and then assign edges to subgraphs. We first prescribe a two-stage cutting plane approach with integer variables in both stages, and examine computational difficulties associated with the proposed cutting planes. As an alternative, we prescribe a hybrid integer programming/constraint programming algorithm capable of solving a suite of test instances within practical computational limits.     

Single machine scheduling to minimize weighted sum of completion times with secondary criterion — A branch and bound approach

Burns presented a counter example to Smith's algorithm and developed a new algorithm which also provides a local optimal for the problem. A Branch and Bound algorithm is presented to produce the global optimal schedule by using elimination rules obtainable from theorems. These rules eliminate branching to a significant extent. Numerical examples illustrate the solution.     

On the Computational Complexity of a Rigidity Problem

Consider a structure of flexible joints connected by rigid bars.These bars will constrain the possible motions of the jointsof this structure. By "pinning down" some of the joints so thatthey cannot move further constraints will be added. In thisway the entire structure can be made rigid. A problem consideredby Bolker & Crapo (1977) and others, is that of findingthe minimum number of joints that must be pinned in order tomake a given two- or three-dimensional structure rigid. We considerthe computational complexity of this problem. Lovasz (1980)gives a somewhat complicated but polynomial time procedure forthis problem in the two-dimensional case. In this paper we showthat in three or more dimensions the problem is NP-complete,and so is unlikely to have a polynomial time algorithm.     

On the enrouting protocol problem under uncertainty

In this paper we present a two-stage stochastic mixed 0–1 dynamic multicommodity model and algorithm for determining the enrouting protocol in the telecommunications network under uncertainty. Given the network connectivity, node processing and buffer and arc flow capacity, the aim is to determine the outgoing arc for the information flow reaching a given node for each destination terminal node (i.e., obtaining the route to be followed by the information flow from each origin terminal node to each destination terminal node). The origin–destination (O–D) flow matrix is given by the number of information packets to be sent from the origin terminal nodes to the destination terminal nodes along a given time horizon, i.e., a call scale. The uncertainty in the O–D flow matrix is treated via a scenario tree approach. The main goal is to minimize a composite function of the expected lost information, a penalization of the deviation from the FIFO strategy on the information flow entering the network, and the expected number of nodes visited by the information packets. A mixture of an enrouting arc generation scheme and a genetic algorithm for obtaining the enrouting protocols over the scenarios is presented. The tool presented in this paper could be used for simulating the enrouting protocols to analyze the saturation of the network, but it has a time constraint for real time operation. Faster algorithms are needed to define the routing tables during the operation stage. Computational experience is reported.     

An effective algorithm for the two-stage location problem on a tree-like network

A two-stage facility location problem on a tree-like network is considered under the restriction that the transportation costs for a unit of production from one node to another is equal to the sum of the edges in the path connecting these nodes. Some exact algorithm with time complexity O(nm ³) is suggested for this problem, where n is the number of the production demand points and, m is an upper bound on the number of possible facility location sites of each stage.     

Algorithme d'encadrement de l'optimum global d'une fonction différentiable

The purpose of the method proposed is to estimate closely the minimum of a multivariate differentiable function and to localize all minimizers. The algorithm, using inclusion properties of interval arithmetic, gives an underestimation of the function; this process, then, may be integrated in a Branch and Bound algorithm, i.e., sub-box branching, elimination, and selection.     

A statistical model for global optimization by means of select and clone

A statistical model tor giobai optimization is constructed generalizing some properties ofthe Wiener process to the multidimensional case. A new approach, which is similar to the Branch and Bound approach, is proposed to the construction of algorithms based on statistical models. A two dimensional version of the algorithm is implemented, and test results are presented     

A composite very large-scale neighborhood structure for the capacitated minimum spanning tree problem

The capacitated minimum spanning tree (CMST) problem is to find a minimum cost spanning tree in a network where nodes have specified demands, with an additional capacity constraints on the subtrees incident to a given source node s. The capacitated minimum spanning tree problem arises as an important subproblem in many telecommunication network design problems. In a recent paper, Ahuja et al. (Math. Program. 91 (2001) 71) proposed two very large-scale neighborhood search algorithms for the capacitated minimum spanning tree problem. Their first node-based neighborhood structure is obtained by performing multi-exchanges involving several trees where each tree contributes a single node. Their second tree-based neighborhood structure is obtained by performing multi-exchanges where each tree contributes a subtree. The computational investigations found that node-based multi-exchange neighborhood gives the best performance for the homogenous demand case (when all nodes have the same demand), and the tree-based multi-exchange neighborhood gives the best performance for the heterogeneous demand case (when nodes may have different demands). In this paper, we propose a composite neighborhood structure that subsumes both the node-based and tree-based neighborhoods, and outperforms both the previous neighborhood search algorithms for solving the capacitated minimum spanning tree problem on standard benchmark instances. We also develop improved dynamic programming based exact algorithms for searching the composite neighborhood.