Volume 4, numéro 1, winter 2009

EN :

This paper describes models and solution algorithms for solving robust multistage decision problems under a special type of uncertainty model referred to here as parsimonious. The main interest of such a model is to provide compact representations of potentially huge scenario trees, leading to efficient dynamic programming-based computation of optimal strategies. Also, contrary to the case of most previously published work on similar problems, which essentially require an independence assumption (on the occurrences of uncertain events in different time periods ) our model handles - and properly exploits - some form of dependence over time via a concept of uncertainty budget constraints. Examples of application are discussed including optimal inventory management and the search for robust shortest paths in directed acyclic graphs. Computational results illustrating and validating the proposed approach are also presented.

EN :

Many IP (Internet Protocol) networks use OSPF (Open Shortest Path First) for determining the routing of traffic. OSPF routers compute routing paths using link weights set by the network administrator, and the routers send traffic on all shortest paths to the destination. An interesting question is whether or not a set of prespecified routing patterns can be realized in an OSPF network. If not, we seek structural properties that explain why no such weights exist. Mathematical models for finding weights and for combining routing patterns are presented. We show that two possibly non-spanning routing patterns forming a “valid cycle” cannot simultaneously be obtained in an OSPF network. Two new methods for finding valid cycles are presented, illustrated by numerical examples, and shown to be faster than those previously known.

EN :

We study on-line models for the set-covering problem in which items from a ground set arrive one by one and with any such item c, the list of names of sets that contain it in the final instance is also presented possibly together with some information regarding the content of such sets. A decision maker has to select which set, among the sets containing c, has to be put in the solution in order to cover the item. Such decision has to be taken before a new item arrives and is irrevocable. The problem consists in minimizing the number of chosen sets. We first analyze some simple heuristics for the model in which only names of sets are provided. Then we show non-trivial matching upper and lower bounds for the competitive ratio in the model in which for any item that arrives the content of all sets containing it is also revealed.

EN :

Shape matrix decomposition is a subproblem in radiation therapy planning. A given fluence matrix A has to be decomposed into a sum of shape matrices corresponding to homogeneous fields that can be shaped by a multileaf collimator (MLC). We solve the problem of minimizing the delivery time for an approximation of A satisfying certain prescribed bounds, under the additional condition that the used MLC requires the interleaf collision constraint.

EN :

Traditional techniques in portfolio management rely on the precise knowledge of the underlying probability distributions; in practice, however, such information is difficult to obtain because multiple factors affect stock prices on a daily basis and unexpected events might affect the price dynamics. To address this issue, we propose an approach to dynamic portfolio management based on the sequential update of stock price forecasts in a robust optimization setting, where the updating process is driven by the historical observations. Forecasts are updated using only the most recent data when the stock price differs significantly from predictions. In this work, we present a robust framework to optimal selling time theory. We introduce a wait-to-decide period, and allow actual price movements to drive the best decision in response to a bad investment. Numerical results illustrate our strategy, which requires less frequent updating of the problem parameters than in the traditional approach while exhibiting promising performance.

EN :

By using the forcing function, we propose a general form of nonmonotone line search technique for unconstrained optimization. The technique includes some well known nonmonotone line search as special cases while independent on the nonmonotone parameter case. We establish the global convergence of the method under weak conditions and we report numerical test results with a modified BFGS method to show the effectiveness of the proposed method.

EN :

This paper addresses the class of nonlinear mixed integer stochastic programming problems. In particular, we consider two-stage problems with nonlinearities both in the objective function and constraints, pure integer first stage and mixed integer second stage variables. We exploit the specific problem structure to develop a global optimization algorithm. The basic idea is to decompose the original problem into smaller manageable optimization subproblems and coordinate their solutions by means of a Branch and Bound approach. Preliminary computational experiments have been carried out on a stochastic version of the Trim Loss problem.