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 work we propose a new problem, that we have named hop-constrained minimum cost flow spanning tree problem, and develop an exact solution methodology. This problem is an extension of the well know NP-hard hop-constrained Minimum Spanning Tree problem (MST), since in addition to finding the arcs to be used we also must find the amount of flow that is to be routed through each arc. The hop-constrained MST has numerous practical applications in the design of communication networks. The hop constraints are usually used to guarantee a certain quality of service with respect to availability, reliability and lower delays, since they limit the number of arcs in each path from the central service provider. Including the flows, as we propose, allows for different levels of service requirements. A further extension is considered: the cost functions may have any type or form, may be neither convex nor concave, and need not to be differentiable or continuous. We develop a dynamic programming approach, which extends the scope of application of a previous work, to solve to optimality such problems. Computational experiments are performed using randomly generated test problems. Results showing the robustness of the method are reported.

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 work, we address investment decisions in production systems by using real options. As is standard in literature, the stochastic variable is assumed to be normally distributed and then approximated by a binomial distribution, resulting in a binomial lattice. The methodology establishes a discrete-valued lattice of possible future values of the underlying stochastic variable (demand in our case) and then, computes the project value. We have developed and implemented stochastic dynamic programming models both for fixed and flexible capacity systems. In the former case, we consider three standard options: the option to postpone investment, the option to abandon investment, and the option to temporarily shut-down production. For the latter case, we introduce the option of corrective action, in terms of production capacity, that the management can take during the project by considering the existence of one of the following: (i) a capacity expansion option; (ii) a capacity contraction option; or (iii) an option considering both expansion and contraction. The full flexible capacity model, where both the contraction and expansion options exist, leads, as expected, to a better project predicted value and thus, investment policy. However, we have also found that the capacity strategy obtained from the flexible capacity model, when applied to specific demand data series, often does not lead to a better investment decision. This might seem surprising, at first, but it can be explained by the inaccuracy of the binomial model. The binomial model tends to undervalue future decreases in the stochastic variable (demand), while at the same time tending to overvalue an increase in future demand values.

Abstract
We propose a Hybrid Genetic Algorithm (HGA) for a combinatorial optimization problem, motivated by, and a simplification of, a TV Self-promotion Assignment Problem. Given the weekly self-promotion space (a set of TV breaks with known duration) and a set of products to promote, the problem consists of assigning the products to the breaks in the "best" possible way. The objective is to maximize contacts in the target audience for each product, whist satisfying all constraints. The HGA developed incorporates a greedy heuristic to initialize part of the population and uses a repair routine to guarantee feasibility of each member of the population. The HGA works on a simplified version of the problem that, nevertheless, maintains its essential features. The proposed simplified problem is a binary programming problem that has similarities with other known combinatorial optimization problems, such as the assignment problem or the multiple knapsack problem, but has some distinctive features that characterize it as a new problem. Although we are mainly interested in solving problems of large dimension (of about 200 breaks and 50 spots), the quality of the solution has been tested on smaller dimension problems for which we are able to find an exact global minimum using a branch-and-bound algorithm. For these smaller dimension problems we have obtained solutions, on average, within 1% of the optimal solution value.

Abstract
In this work we address the Singe-Source Uncapacitated Minimum Cost Network Flow Problem with concave cost functions. Given that this problem is of a combinatorial nature and also that the total costs are nonlinear, we propose a hybrid heuristic to solve it. In this type of algorithms one usually tries to manage two conflicting aspects of searching behaviour: exploration, the algorithm's ability to search broadly through the search space; and exploitation, the algorithm ability to search locally around good solutions that have been found previously. In our case, we use an Ant Colony Optimization algorithm to mainly deal with the exploration, and a Local Search algorithm to cope with the exploitation of the search space. Our method proves to be very efficient while solving both small and large size problem instances. The problems we have used to test the algorithm were previously solved by other authors using other population based heuristics and our algorithm was able to improve upon their results, both in terms of computing time and solution quality.