Volume 5, numéro 2, fall 2010

EN :

We study the problem of computing general static-arbitrage bounds for European basket options; that is, computing bounds on the price of a basket option, given the only assumption of absence of arbitrage, and information about prices of other European basket options on the same underlying assets and with the same maturity. In particular, we provide a simple efficient way to compute this type of bounds by solving a large finite non-linear programming formulation of the problem. This is done via a suitable Dantzig-Wolfe decomposition that takes advantage of an integer programming formulation of the corresponding subproblems. Our computation method equally applies to both upper and lower arbitrage bounds, and provides a solution method for general instances of the problem. This constitutes a substantial contribution to the related literature, in which upper and lower bound problems need to be treated differently, and which provides efficient ways to solve particular static-arbitrage bounds for European basket options; namely, when the option prices information used to compute the bounds is limited to vanilla and/or forward options, or when the number of underlying assets is limited to two assets. Also, our computation method allows the inclusion of real-world characteristics of option prices into the arbitrage bounds problem, such as the presence of bid-ask spreads. We illustrate our results by computing upper and lower arbitrage bounds on gasoline/heating oil crack spread options.

EN :

Column generation algorithms have been specially designed for solving mathematical programs with a huge number of variables. Unfortunately, this method suffers from slow convergence that limits its efficiency and usability. Several accelerating approaches are proposed in the literature such as stabilization-based techniques. A more classical approach, known as “intensification”, consists in inserting a set of columns instead of only the best one. Unfortunately, this intensification typically overloads the master problem, and generates a huge number of useless variables. This article covers some characteristics of the generated columns from theoretical and experimental points of view. Two selection criteria are compared. The first one is based on column reduced cost and the second on column structure. We conclude our study with computational experiments on two kinds of problems: the acyclic vehicle routing problem with time windows and the one-dimensional cutting stock problem.

EN :

We show how a technique from signal processing known as zero-delay convolution can be used to develop more efficient dynamic programming algorithms for a broad class of stochastic optimization problems. This class includes several variants of discrete stochastic shortest path, scheduling, and knapsack problems, all of which involve making a series of decisions over time that have stochastic consequences in terms of the temporal delay between successive decisions. We also correct a flaw in the original analysis [8] of the zero-delay convolution algorithm.

EN :

We consider the graph center problem in the joinsemilattice L(T ) of all subtrees of a tree T . A subtree S of a tree T is a central subtree of T if S has the minimum eccentricity in the joinsemilattice. The graph center of the joinsemilattice is the set of all central subtrees. A central subtree with the minimum number of points is a least central subtree of a tree T . Thus least central subtrees of T are, in some sense, the best possible connected substructures of T among all connected substructures. We show that every tree is a unique least central subtree of some larger tree. Our main result points out the importance of the cardinality of the nodes of degree two. Low cardinality guarantees uniqueness and explicit construction for the least central subtree.

EN :

In the present paper we consider a particular case of the segmentation problem arising in the elaboration of radiation therapy plans. This problem consists in decomposing an integer matrix A into a nonnegative integer linear combination of some particular binary matrices called segments which represent fields that are deliverable with a multileaf collimator. For the radiation therapy context, it is desirable to find a decomposition that minimizes the beam-on time, that is the sum of the coefficients of the decomposition. Here we investigate a variant of this minimization problem with an additional constraint on the segments, called the tongue-and-groove constraint. Although this minimization problem under the condition that the used segments have to respect the tongue-and-groove constraint has already been studied, the complexity of it is still unknown. Here we prove that in the particular case where A is a binary matrix this problem is polynomially solvable. We provide a polynomial procedure that finds such a decomposition with minimal beam-on time. Furthermore, we show that the beam-on time of an optimal decomposition (but not the segmentation itself) can be found by determining the chromatic number of a related perfect graph.

EN :

Consider a project which consists in a set of operations to be performed, assuming the processing time of each operation is at most one time period. In this project, precedence and incompatibility constraints between operations have to be satisfied. The goal is to assign a time period to each operation while minimizing the duration of the whole project and while taking into account all the constraints. Based on the mixed graph coloring model and on an efficient and quick tabu search algorithm for the usual graph coloring problem, we propose a tabu search algorithm as well as a variable neighborhood search heuristic for the considered scheduling problem. We formulate an integer linear program (useful for the CPLEX solver) as well as a greedy procedure for comparison considerations. Numerical results are reported on instances with up to 500 operations.