Designing a network able to route a set of non-simultaneous demand vectors is an important problem arising in telecommunications. In this paper, we compare the optimal capacity allocation costs for six routing sets: affine routing, volume routing and its two simplifications, the routing based on an unrestricted 2-cover of the uncertainty set, and the routing … Read more
We study stochastic linear programming games: a class of stochastic cooperative games whose payoffs under any realization of uncertainty are determined by a specially structured linear program. These games can model a variety of settings, including inventory centralization and cooperative network fortification. We focus on the core of these games under an allocation scheme that … Read more
In this paper we present some algorithms for solving a number of new models of facility location involving sets which generalize the classical Fermat-Torricelli problem. Our approach uses subgradient-type algorithms to cope with nondi erentiabilty of the distance functions therein. Another approach involves approximating nonsmooth optimization problems by smooth optimizations problems using Nesterov’s smoothing techniques. Convergence … Read more
It is often the case that the computed optimal solution of an optimization problem cannot be implemented directly, irrespective of data accuracy, due to either (i) technological limitations (such as physical tolerances of machines or processes), (ii) the deliberate simplification of a model to keep it tractable (by ignoring certain types of constraints that pose … Read more
We consider the following freight train routing problem (FTRP). Given is a transportation network with fixed routes for passenger trains and a set of freight trains (requests), each defined by an origin and destination station pair. The objective is to calculate a feasible route for each freight train such that a sum of all expected … Read more
Network analysis is of great interest for the study of social, biological and technological networks, with applications, among others, in business, marketing, epidemiology and telecommunications. Researchers are often interested in assessing whether an observed feature in some particular network is expected to be found within families of networks under some hypothesis (named conditional random networks, … Read more
We propose a scenario decomposition algorithm for stochastic 0-1 programs. The algorithm recovers an optimal solution by iteratively exploring and cutting-off candidate solutions obtained from solving scenario subproblems. The scheme is applicable to quite general problem structures and can be implemented in a distributed framework. Illustrative computational results on standard two-stage stochastic integer programming and … Read more
We analyze the properties of the optimal portfolio policy for a multiperiod mean-variance investor facing multiple risky assets in the presence of general transaction costs such as proportional, market impact, and quadratic transaction costs. For proportional transaction costs, we find that a buy-and-hold policy is optimal: if the starting portfolio is outside a parallelogram-shaped no-trade … Read more
In the context of sequential methods for solving general nonlinear programming problems, it is usual to work with augmented subproblems instead of the original ones, tackled by the $\ell_1$-penalty function together with the shortcut usage of a convenient penalty parameter. This paper addresses the theoretical reasoning behind handling the original subproblems by such an augmentation … Read more
In this note we present tight lower bounds on the information-based complexity of large-scale smooth convex minimization problems. We demonstrate, in particular, that the k-step Conditional Gradient (a.k.a. Frank-Wolfe) algorithm as applied to minimizing smooth convex functions over the n-dimensional box with n ≥ k is optimal, up to an O(ln n)-factor, in terms of … Read more