FEASIBILITY IN TRANSPORTATION NETWORKS WITH SUPPLY EATING ARCS

In this paper, we consider a special case of a new type of mixed integ er programming problem: the Transportation Network with Supply Eating Arcs, This problem arises from an application in intelligent [telecomm unications] networks (IN). It contains within its definition many clas sical mixed integer programming problems. The problem is defined as a transportation network with an additional condition. For an are to hav e positive flow, the node capacity of its originating node (i.e., a su pply node) is decreased by a fixed amount depending on the are. The sp ecial case that we consider is where this fixed amount is solely depen dent on the demand node to which the are is incident. In studying this problem, we are mainly interested in the feasibility of such problems and focus our attention on this aspect here. We discuss why finding a feasible solution is potentially difficult as well as various methods for finding one. In particular, we describe a set of solutions (in te rms of solution structure) that always contains a feasible solution, i f one exists. We then describe a method for finding a feasible solutio n based on enumerating this set. The main advantage of the solution pr ocedure is that at no time do we need to explicitly solve an LP (or ev en a transportation problem). (C) 1998 John Wiley & Sons, Inc.