Capacitated,balanced, sequential location-allocation problems on chains and trees

This paper considers finite horizon, multiperiod, sequential, minisum location-allocation problems on chain graphs and tree networks. The demand has both deterministic and probabilistic components, and increases dynamically from period to period. The problem is to locate one additionalcapacitated facility in each of thep specified periods, and to determine the service allocations of the facilities, in order to optimally satisfy the demand on the network. In this context, two types of objective criteria or location strategies are addressed. The first is a myopic strategy in which the present period cost is minimized sequentially for each period, and the second is a discounted present worth strategy. For the chain graph, we analyze ap-facility problem under both these criteria, while for the tree graph, we analyze a 3-facility myopic problem, and a 2-facility discounted present worth problem. All these problems are nonconvex, and we specify a finite set of candidate solutions which may be compared in order to determine a global optimal solution.     

Thep-facility ordered median problem on networks

In this paper we deal with the ordered median problem: a family of location problems that allows us to deal with a large number of real situations which does not fit into the standard models of location analysis. Moreover, this family includes as particular instances many of the classical location models. Here, we analyze thep-facility version of this problem on networks and our goal is to study the structure of the set of candidate points to be optimal solutions. The research of the authors is partially financed by Spanish research grants BFM2001-2378, BFM2001-4028, BFM2004-0909 and HA2003-0121.     

The multicriteria p-facility median location problem on networks

In this paper we discuss the multicriteria p-facility median location problem on networks with positive and negative weights. We assume that the demand is located at the nodes and can be different for each criterion under consideration. The goal is to obtain the set of Pareto-optimal locations in the graph and the corresponding set of non-dominated objective values. To that end, we first characterize the linearity domains of the distance functions on the graph and compute the image of each linearity domain in the objective space. The lower envelope of a transformation of all these images then gives us the set of all non-dominated points in the objective space and its preimage corresponds to the set of all Pareto-optimal solutions on the graph. For the bicriteria 2-facility case we present a low order polynomial time algorithm. Also for the general case we propose an efficient algorithm, which is polynomial if the number of facilities and criteria is fixed.     

Network location problems with continuous link demands: p-medians on a chain and 2-medians on a tree

This paper is concerned with minisum location-allocation problems on undirected networks in which demands can occur on links with uniform probability distributions. Two types of networks are considered. The first type considered is simply a chain graph. It is shown that except for the 1-median case, the problem is generally non-convex. However, for the p-median case, a discrete set of potential optimal facility locations may be identified, and hence it is shown that all local and global minima to the problem may be discovered by solving a series of trivial linear programming problems. This analysis is then extended to prescribe an algorithm for the 2-median location-allocation problem on a tree network involving uniform continuous demands on links. Some localization theorems are presented in the spirit of the work done on discrete nodal demand problems.     

A comparative study of approaches to dynamic location problems

We compare the performance of seven approximate methods for locating new capacity over time to minimize the total discounted costs of meeting growing demands at several locations. Comparisons are based on results for two industrial planning problems from India, and are given for both discrete-time and continuous-time frameworks. We also discuss strategies for combining different methods into possibly more effective hybrid approaches.     

Using scenario trees and progressive hedging for stochastic inventory routing problems

The Stochastic Inventory Routing Problem is a challenging problem, combining inventory management and vehicle routing, as well as including stochastic customer demands. The problem can be described by a discounted, infinite horizon Markov Decision Problem, but it has been showed that this can be effectively approximated by solving a finite scenario tree based problem at each epoch. In this paper the use of the Progressive Hedging Algorithm for solving these scenario tree based problems is examined. The Progressive Hedging Algorithm can be suitable for large-scale problems, by giving an effective decomposition, but is not trivially implemented for non-convex problems. Attempting to improve the solution process, the standard algorithm is extended with locking mechanisms, dynamic multiple penalty parameters, and heuristic intermediate solutions. Extensive computational results are reported, giving further insights into the use of scenario trees as approximations of Markov Decision Problem formulations of the Stochastic Inventory Routing Problem.     

Optimal myopic policies and index policies for stochastic scheduling problems

Stochastic scheduling problems are considered by using discounted dynamic programming. Both, maximizing pure rewards and minimizing linear holding costs are treated in one common Markov decision problem. A sufficient condition for the optimality of the myopic policy for finite and infinite horizon is given. For the infinite horizon case we show the optimality of an index policy and give a sufficient condition for the index policy to be myopic. Moreover, the relation between the two sufficient conditions is discussed.     

Approximating the Minimum-Degree Steiner Tree to within One of Optimal

The problem of constructing a spanning tree for a graph G = (V, E) with n vertices whose maximal degree is the smallest among all spanning trees of G is considered. This problem is easily shown to be NP-hard. In the Steiner version of this problem, along with the input graph, a set of distinguished vertices D V is given. A minimum-degree Steiner tree is a tree of minimum degree which spans at least the set D. Iterative polynomial time approximation algorithms for the problems are given. The algorithms compute trees whose maximal degree is at most Δ* + 1, where Δ* is the degree of some optimal tree for the respective problems. Unless P = NP, this is the best bound achievable in polynomial time.     

Inventory sharing in integrated network design and inventory optimization with low-demand parts

Service Parts Logistics (SPL) problems induce strong interaction between network design and inventory stocking due to high costs and low demands of parts and response time based service requirements. These pressures motivate the inventory sharing practice among stocking facilities. We incorporate inventory sharing effects within a simplified version of the integrated SPL problem, capturing the sharing fill rates in 2-facility inventory sharing pools. The problem decides which facilities in which pools should be stocked and how the demand should be allocated to stocked facilities, given full inventory sharing between the facilities within each pool so as to minimize the total facility, inventory and transportation costs subject to a time-based service level constraint. Our analysis for the single pool problem leads us to model this otherwise non-linear integer optimization problem as a modified version of the binary knapsack problem. Our numerical results show that a greedy heuristic for a network of 100 facilities is on average within 0.12% of the optimal solution. Furthermore, we observe that a greater degree of sharing occurs when a large amount of customer demands are located in the area overlapping the time windows of both facilities in 2-facility pools.     

Network flow interdiction on planar graphs

The network flow interdiction problem asks to reduce the value of a maximum flow in a given network as much as possible by removing arcs and vertices of the network constrained to a fixed budget. Although the network flow interdiction problem is strongly NP-complete on general networks, pseudo-polynomial algorithms were found for planar networks with a single source and a single sink and without the possibility to remove vertices. In this work, we introduce pseudo-polynomial algorithms that overcome various restrictions of previous methods. In particular, we propose a planarity-preserving transformation that enables incorporation of vertex removals and vertex capacities in pseudo-polynomial interdiction algorithms for planar graphs. Additionally, a new approach is introduced that allows us to determine in pseudo-polynomial time the minimum interdiction budget needed to remove arcs and vertices of a given network such that the demands of the sink node cannot be completely satisfied anymore. The algorithm works on planar networks with multiple sources and sinks satisfying that the sum of the supplies at the sources equals the sum of the demands at the sinks. A simple extension of the proposed method allows us to broaden its applicability to solve network flow interdiction problems on planar networks with a single source and sink having no restrictions on the demand and supply. The proposed method can therefore solve a wider class of flow interdiction problems in pseudo-polynomial time than previous pseudo-polynomial algorithms and is the first pseudo-polynomial algorithm that can solve non-trivial planar flow interdiction problems with multiple sources and sinks. Furthermore, we show that the k-densest subgraph problem on planar graphs can be reduced to a network flow interdiction problem on a planar graph with multiple sources and sinks and polynomially bounded input numbers.     

An optimal time algorithm for finding a maximum weight independent set in a tree

The maximum weight independent set problem for a general graph is NP-hard. But for some special classes of graphs, polynomial time algorithms do exist for solving it. Based on the divide-and-conquer strategy, Pawagi has presented anO(|V|log|V|) time algorithm for solving this problem on a tree. In this paper, we propose anO(|V|) time algorithm to improve Pawagi's result. The proposed algorithm is based on the dynamic programming strategy and is time optimal within a constant factor.     

A correction to the definition of local center

It is known that in order to solve the minimax facility location problem on a graph with a finite set of demand points, only a finite set of possible location points, called ‘local centers’ must be considered.It has been shown that the continuous m-center problem on a graph can be solved by using a series of set covering problems in which each local center covers the demand points at a distance not greater than a corresponding number called ‘the range’ of the local center.However, all points which are at the same distance from more than two demand points, and from which there is no direction where all these distances are decreasing, must also be considered as local centers. This paper proves that, in some special cases, it is not sufficient to consider only the points where this occurs with respect to pairs of demand points. The definition of local center is corrected and the corresponding results and algorithms are revised.     

Gradient-constrained discounted Steiner trees II: optimally locating a discounted Steiner point

A gradient-constrained discounted Steiner tree is a network interconnecting given set of nodes in Euclidean space where the gradients of the edges are all no more than an upper bound which defines the maximum gradient. In such a tree, the costs are associated with its edges and values are associated with nodes and are discounted over time. In this paper, we study the problem of optimally locating a single Steiner point in the presence of the gradient constraint in a tree so as to maximize the sum of all the discounted cash flows, known as the net present value (NPV). An edge in the tree is labelled as a b edge, or a m edge, or an f edge if the gradient between its endpoints is greater than, or equal to, or less than the maximum gradient respectively. The set of edge labels at a discounted Steiner point is called its labelling. The optimal location of the discounted Steiner point is obtained for the labellings that can occur in a gradient-constrained discounted Steiner tree. In this paper, we propose the gradient-constrained discounted Steiner point algorithm to optimally locate the discounted Steiner point in the presence of a gradient constraint in a network. This algorithm is applied to a case study. This problem occurs in underground mining, where we focus on the optimization of underground mine access to obtain maximum NPV in the presence of a gradient constraint. The gradient constraint defines the navigability conditions for trucks along the underground tunnels.     

Locating the two-median of a tree network with continuous link demands

Typical formulations of thep-median problem on a network assume discrete nodal demands. However, for many problems, demands are better represented by continuous functions along the links, in addition to nodal demands. For such problems, optimal server locations need not occur at nodes, so that algorithms of the kind developed for the discrete demand case can not be used. In this paper we show how the 2-median of a tree network with continuous link demands can be found using an algorithm based on sequential location and allocation. We show that the algorithm will converge to a local minimum and then present a procedure for finding the global minimum solution.     

The optimality of myopic stocking policies for systems with decreasing purchasing prices

This paper studies the stocking/replenishment decisions for inventory systems where the purchasing price of an item decreases overtime. In a periodic review setting with stochastic demands, we model the purchasing prices of successive periods as a stochastic and decreasing sequence. To minimize the expected total discounted costs (purchasing, inventory holding and shortage penalty) for systems with backlogging and lost sales, we derive conditions, regarding the cost parameters, under which myopic stocking policies are optimal.     

Algorithms for solving multiobjective discrete control problems and dynamic c-games on networks

In this paper we study a special class of multiobjective discrete control problems on dynamic networks. We assume that the dynamics of the system is controlled by p actors (players) and each of them intend to minimize his own integral-time cost by a certain trajectory. Applying Nash and Pareto optimality principles we study multiobjective control problems on dynamic networks where the dynamics is described by a directed graph.Polynomial-time algorithms for determining the optimal strategies of the players in the considered multiobjective control problems are proposed exploiting the special structure of the underlying graph. Properties of time-expanded networks are characterized. A constructive scheme which consists of several algorithms is presented.     

A PTAS for minimum <Emphasis Type="Italic">d</Emphasis>-hop connected dominating set in growth-bounded graphs

In this paper, we design the first polynomial time approximation scheme for d-hop connected dominating set (d-CDS) problem in growth-bounded graphs, which is a general type of graphs including unit disk graph, unit ball graph, etc. Such graphs can represent majority types of existing wireless networks. Our algorithm does not need geometric representation (e.g., specifying the positions of each node in the plane) beforehand. The main strategy is clustering partition. We select the d-CDS for each subset separately, union them together, and then connect the induced graph of this set. We also provide detailed performance and complexity analysis.     

A polynomial method for the pos/neg weighted 3-median problem on a tree

Let a connected undirected graph G  =  (V, E) be given. In the classical p-median problem we want to find a set X containing p points in G such that the sum of weighted distances from X to all vertices in V is minimized. We consider the semi-obnoxious case where every vertex has either a positive or negative weight. In this case we have two different objective functions: the sum of the minimum weighted distances from X to all vertices and the sum of the weighted minimum distances. In this paper we show that for the case p = 3 an optimal solution for the second model in a tree can be found in O(n ⁵) time. If the 3-median is restricted to vertices or if the tree is a path then the complexity can be reduced to O(n ³). This research has partially been supported by the Spezialforschungsbereich F 003 “Optimierung und Kontrolle”, Projektbereich Diskrete Optimierung.     

On the complexity of loading shallow neural networks

We formalize a notion of loading information into connectionist networks that characterizes the training of feed-forward neural networks. This problem is NP-complete, so we look for tractable subcases of the problem by placing constraints on the network architecture. The focus of these constraints is on various families of “shallow” architectures which are defined to have bounded depth and un-bounded width. We introduce a perspective on shallow networks, called the Support Cone Interaction (SCI) graph, which is helpful in distinguishing tractable from intractable subcases: When the SCI graph is a tree or is of limited bandwidth, loading can be accomplished in polynomial time; when its bandwidth is not limited we find the problem NP-complete even if the SCI graph is a simple 2-dimensional planar grid.     

Expected hitting and cover times of random walks on some special graphs

We give general bounds (and in some cases exact values) for the expected hitting and cover times of the simple random walk on some special undirected connected graphs using symmetry and properties of electrical networks. In particular we give easy proofs for an N–1H_N-1 lower bound and an N² upper bound for the cover time of symmetric graphs and for the fact that the cover time of the unit cube is Φ(NlogN). We giver a counterexample to a conjecture of Freidland about a general bound for hitting times. Using the electric approach, we provide some genral upper and lower bounds for the expected cover times in terms of the diameter of the graph. These bounds are tight in many instances, particularly when the graph is a tree. © 1994 John Wiley & Sons, Inc.