Abstract

Abstract
In this paper a Branch-and-Bound (BB) algorithm is developed to obtain an optimal solution to the single source uncapacitated minimum cost Network Flow Problem (NFP) with general concave costs. Concave NFPs are NP-Hard, even for the simplest version therefore, there is a scarcity of exact methods to address them in their full generality. The BB algorithm presented here can be used to solve optimally single source uncapacitated minimum cost NFPs with any kind of concave arc costs. The bounding is based on the computation of lower bounds derived from state space relaxations of a dynamic programming formulation. The relaxations, which are the subject of the paper (Fontes et al., 2005b) and also briefly discussed here, involve the use of non-injective mapping functions, which guarantee a reduction on the cardinality of the state space. Branching is performed by either fixing an arc as part of the final solution or by removing it from the final solution. Computational results are reported and compared to available alternative methods for addressing the same type of problems. It could be concluded that our BB algorithm has better performance and the results have also shown evidence that it has a sub-exponential time growth.

Abstract
In this paper we obtain Lower Bounds (LBs) to concave cost network flow problems. The LBs are derived from state space relaxations of a dynamic programming formulation, which involve the use of non-injective mapping functions guaranteing a reduction on the cardinality of the state space. The general state space relaxation procedure is extended to address problems involving transitions that go across several stages, as is the case of network flow problems. Applications for these LBs include: estimation of the quality of heuristic solutions; local search methods that use information of the LB solution structure to find initial solutions to restart the search (Fontes et al., 2003, Networks, 41, 221-228); and branch-and-bound (BB) methods having as a bounding procedure a modified version of the LB algorithm developed here, (see Fontes et al., 2005a). These LBs are iteratively improved by penalizing, in a Lagrangian fashion, customers not exactly satisfied or by performing state space modifications. Both the penalties and the state space are updated by using the subgradient method. Additional constraints are developed to improve further the LBs by reducing the searchable space. The computational results provided show that very good bounds can be obtained for concave cost network flow problems, particularly for fixed-charge problems.

Abstract
In this paper, we describe a dynamic programming approach to solve optimally the single-source uncapacitated minimum cost network flow problem with general concave costs. This class of problems is known to be NP-Hard and there is a scarcity of methods to solve them in their full generality. The algorithms previously developed critically depend on the type of cost functions considered and on the number of nonlinear arc costs. Here, a new dynamic programming approach that does not depend on any of these factors is proposed. Computational experiments were performed using randomly generated problems. The computational results reported for small and medium size problems indicate the effectiveness of the proposed approach.

Abstract
In this paper we extend M. Lyubich's recent results on the global hyperbolicity of renormalization of quadratic-like germs to the space of C-r unimodal maps with quadratic critical point. We show that in this space the bounded-type limit sets of the renormalization operator have an invariant hyperbolic structure provided r >= 2 + alpha with alpha close to one. As an intermediate step between Lyubich's results and ours, we prove that the renormalization operator is hyperbolic in a Banach space of real analytic maps. We construct the local stable manifolds and prove that they form a continuous lamination whose leaves are C-1 codimension one, Banach submanifolds of the ambient space, and whose holonom is C1+beta for some beta > 0. We also prove that the global stable sets are C-1 immersed (codimension one) submanifolds as well, provided r >= 3 + alpha with alpha close to one. As a corollary, we deduce that in generic, one-parameter families of C-r unimodal maps, the set of parameters corresponding to infinitely renormalizable maps of bounded combinatorial type is a Cantor set with Hausdorff dimension less than one(1).

Abstract
We consider a symmetric Stackelberg model in which there is asymmetric demand information owned by first and second movers. We analyse the advantages of leadership and flexibility, and prove that when the leading firm faces demand uncertainty, but the follower does not, the first mover does not necessarily have advantage over the second mover. Moreover, we show that the advantage of one firm over the other depends upon the demand fluctuation and also upon the degree of substitutability of the products.