A Dynamic Programming Algorithm for the Fused Lasso and L 0-Segmentation

We propose a dynamic programming algorithm for the one-dimensional Fused Lasso Signal Approximator (FLSA). The proposed algorithm has a linear running time in the worst case. A similar approach is developed for the task of least squares segmentation, and simulations indicate substantial performance improvement over existing algorithms. Examples of R and C implementations are provided in the online Supplementary materials, posted on the journal web site.     

Some applications of L2-hedging with a non-negative wealth process

We consider the problem of L ²-hedging of contingent claims in diffusion type models for securities markets. In contrast to a recent paper of Schweizer (1994) we insist on a non-negative wealth process corresponding to the optimal hedge portfolio. For this reason the usual projection methods cannot be applied. We give some applications of L ²-hedging in this setting including hedging under constraints, a problem of approximating the wealth process of a richer investor and a mean-variance version of it.     

Mathematical Analysis of caching policies and cooperation in YouTube-like services

Currently, most video on-demand services offered over the Internet do not exploit the idle resources available from end-users. We discuss the benefits of user-assistance in video on-demand systems, where users are both clients and servers, helping with the task of video distribution. The mathematical machinery for the systematic analysis of video on-demand services is not mature yet. In this paper we develop a deterministic fluid model to determine the expected evolution of user-assisted on-demand video streaming services. We theoretically prove that cooperative systems always outperform non-cooperative solutions. A combinatorial optimization problem is proposed, where the goal is to distribute a set of video items into repositories trying to offer the minimum waiting times to end-users. This combinatorial problem is proved to be in the class of NP-Complete computational problem, and is heuristically solved with a GRASP methodology. Predictions inspired in YouTube scenarios suggest the introduction of cooperation is both robust and extremely attractive from an economical viewpoint as well.     

A Branch-and-price Algorithm for the Multi-Vehicle Covering Tour Problem

In this paper, we propose a Branch-and-price (BP) algorithm and a Column Generation Heuristic (CGH) for the Multi-Vehicle Covering Tour Problem (m-CTP). Specific dominance and extension pruning rules are introduced to accelerate the resolution of the pricing problems. To the best of our knowledge, this is the first work dedicated to the exact resolution of m-CTP. The algorithm managed to solve about 30% of the instances in our test bed, within a 4 hour CPU time limit. Our preliminary computational experiments suggest that both the lower bounds provided by the formulation behind BP and the CGH upper bounds are of good quality.     

Effective Relaxations and Partitioning Schemes for Solving Water Distribution Network Design Problems to Global Optimality

In this paper, we address the development of a global optimization procedure for the problem of designing a water distribution network, including the case of expanding an already existing system, that satisfies specified flow demands at stated pressure head requirements. The proposed approach significantly improves upon a previous method of Sherali et al. (1998) by way of adopting tighter polyhedral relaxations, and more effective partitioning strategies in concert with a maximal spanning tree-based branching variable selection procedure. Computational experience on three standard test problems from the literature is provided to evaluate the proposed procedure. For all these problems, proven global optimal solutions within a tolerance of 10^–4% and/or within 1$ of optimality are obtained. In particular, the two larger instances of the Hanoi and the New York test networks are solved to global optimality for the very first time in the literature. A new real network design test problem based on the Town of Blacksburg Water Distribution System is also offered to be included in the available library of test cases, and related computational results are presented.     

Multicommodity long-term hydrogeneration optimization with capacity and energy constraints

The work presented deals with long-term hydrogeneration optimization in integrated systems when there are no limitations on the availability of fuels for thermal units. A multicommondity network model represents hydrovariables. Hydrogeneration and its unavailability distribution is modeled as a multiblock distribution and a procedure is derived to convolve the hydropower unavailability distribution with the load duration curve. A suitable approximation of the expected production cost is minimized subject to multicommodity network constraints and to hydropower capacity and hydroenergy limit nonlinear constraints. It can be applied to systems with hydrogeneration regardless of its proportion of hydrothermal mix. A realistic case example is solved and the results are discussed. Simulation tests performed with many inflow sequences validate the results obtained.     

On safe tractable approximations of chance constraints

A natural way to handle optimization problem with data affected by stochastic uncertainty is to pass to a chance constrained version of the problem, where candidate solutions should satisfy the randomly perturbed constraints with probability at least 1 − ?. While being attractive from modeling viewpoint, chance constrained problems “as they are” are, in general, computationally intractable. In this survey paper, we overview several simulation-based and simulation-free computationally tractable approximations of chance constrained convex programs, primarily, those of chance constrained linear, conic quadratic and semidefinite programming.     

An Inverse Problem in Periodic Diffractive Optics: Reconstruction of Lipschitz Grating Profiles

We consider the problem of recovering a two-dimensional periodic structure from scattered waves measured above the structure. Following an approach by Kirsch and Kress, this inverse problem is reformulated as a nonlinear optimization problem. We develop a theoretical basis for the reconstruction method in the case of an arbitrary Lipschitz grating profile. The convergence analysis is based on new perturbation and stability results for the forward problem.     

A Foreground–Background queueing model with speed or capacity modulation

Two models involving a foreground and a background queue are studied in the steady state. Service is provided either by a single server whose speed depends on the total number of jobs present, or by several parallel servers whose number may be controlled dynamically. Job service times have a two-phase Coxian distribution. Incoming jobs join the foreground queue where they execute phase 1, and then possibly move to the background queue for the second phase at lower priority. The trade-offs between holding and energy consumption costs are examined by means of a suitable cost function. Two different two-dimensional Markov processes are solved exactly. The solutions are used in several numerical experiments, aimed at illustrating different aspects of system behaviour.     

Stochastic joint replenishment problem under a fill rate constraint with controllable lead times and shared cost allocation

In a family of items under coordinated inventory replenishments, some products may be replenished at the same time, which in turn implies that some lead time components and costs may be shared among them. This paper investigates this aspect in the context of the joint replenishment problem under the class of cyclic policies, assuming random demands and controllable lead times, and imposing a fill rate constraint for each item.