Volume 6, numéro 1, spring 2011

EN :

Radio Frequency (RF) pulses cause elevated patient temperatures during Magnetic Resonance Imaging (MRI) procedures. Generalized Variable Rate Selective Excitation (gVERSE) is a co-design method for Radio Frequency (RF) pulse and slice gradient which minimizes Specific Absorption Rate (SAR) (the accepted predictor of patient heating). After developing a rigorous mathematical model, the nonlinear gVERSE optimization problem is solved using two competitive software packages. The gVERSE solutions generated by Sparse Optimal Control Software (SOCS) and AMPL–MINOS produce two separate variations of SAR reducing pulses. The different software solutions are compared using numerical simulations of slice selection. The computational experiments involved with the gVERSE model provided insight towards using different software to solve highly demanding mathematical optimization problems.

EN :

An Alternating Intensification/Diversification (AID) method is proposed to tackle global optimization problems, focusing here on global function minimization over continuous variables. Our method is a local search procedure that is particularly easy to implement, and can readily be embedded as a supporting strategy within more sophisticated methods that make use of population-based designs. We perform computational tests comparing the AID method to 20 other algorithms, many of them representing a similar or higher level of sophistication, on a total of 28 benchmark functions. The results show that the new approach generally obtains good quality solutions for unconstrained global optimization problems, suggesting the utility of its underlying notions and the potential value of exploiting its multiple avenues for generalization.

EN :

We consider a generalization of the well known greedy algorithm, called m-step greedy algorithm, where m elements are examined in each iteration. When m = 1 or 2, the algorithm reduces to the standard greedy algorithm. For m = 3 we provide a complete characterization of the independence system, called trioid, where the m-step greedy algorithm guarantees an optimal solution for all weight functions. We also characterize the trioid polytope and propose a generalization of submodular functions.

EN :

One approach to finding a maximum stable set (MSS) in a graph is to try to reduce the size of the problem by transforming the problem into an equivalent problem on a smaller graph. This paper introduces several new reductions for the MSS problem, extends several well-known reductions to the maximum weight stable set (MWSS) problem, demonstrates how reductions for the generalized stable set problem can be used in conjunction with probing to produce powerful new reductions for both the MSS and MWSS problems, and shows how hypergraphs can be used to expand the capabilities of clique projections. The effectiveness of these new reduction techniques are illustrated on the DIMACS benchmark graphs, planar graphs, and a set of challenging MSS problems arising from Steiner Triple Systems.

EN :

In this paper, we consider the classical NP-complete VERTEX COVER problem in large graphs. We assume that the size and the access to the input graph impose the following constraints: (1) the input graph must not be modified (integrity of the input instance), (2) the computer running the algorithm has a memory of limited size (compared to the graph) and (3) the result must be sent to an output memory once a new piece of solution is calculated. Despite the severe constraints of the model, we propose three algorithms that satisfy them. We derive exact formulas giving the expected size of the solution they return. This allows us to compare them, in an analytic way. Then, we consider their complexities. We give exact formulas expressing the expected number of requests they perform on the input graph. Again, we compare them analytically. For both comparisons, we show that none of them is better than the two others.

The formulas we give can help users to estimate the best balance between quality of the solution and performance.