Search

International audience; Communication satellites have the crucial role to forward signals to customers. They filter and amplify uplink signals coming from Earth stations to improve the signal quality before reaching customers. These operations are performed by the payload component of the satellite that embeds reconfigurable components (e.g., switches). These components route signals to appropriate signal processing components (e.g., amplifiers, filters) and lead amplified signals to the output antenna. In order to route the channels that compose signals, satellite engineers can remotely modify switch states. These are typically updated when one or more new channels must be connected or when failures occur. However, satellites embed always more switches to answer customer demands, which makes their reconfiguration time consuming and error prone without appropriate decision aid tools. Power transmission is a crucial objective to ensure a maximum quality of service at reasonable cost. This is why satellite operators aim at minimizing incoming power signals while guaranteeing a maximum factor of amplification at the output antenna. This problem is referred to as the “satellite payload power problem.” Previous works have outlined the difficulty to solve exactly large instances of this problem. This work proposes to improve the existing mathematical formulation of the switch network. We show that it can be modeled as a static network and switch states can be deduced after optimization, thus limiting the combinatorial explosion. Computational experiments on different sizes of realistic instances using the adaptive ε‐constraint method demonstrate the computational time gain with this new model and the possibility to solve larger instances.

International audience; We propose in this paper a new Dantzig-Wolfe master model based on Lagrangian decomposition. We establish the relationship with classical Dantzig-Wolfe decomposition master problem and propose an alternative proof of the dominance of Lagrangian decomposition on Lagrangian relaxation dual bound. As illustration, we give the corresponding models and numerical results for two standard mathematical programs: the 0-1 bidimensional knapsack problem and the generalized assignment problem.

International audience; An efficient use of dynamic programming requires a substantial reduction of the number of labels. We propose in this paper an efficient way of reducing the number of labels saved and dominance computing time. Our approach is validated by experiments on shortest path problem with time windows instances.

We want to solve exactly large instances of the 0-1 quadratic knapsack problem with a branch-and-bound algorithm. Thus we need to obtain good lower and upper bounds in order to fix variables in the preprocessing phase at the root node of the search tree. We introduce reoptimization technics in this preprocessing phase using the lagrangian relaxation of Caprara, Pisinger and Toth and the lagrangian decomposition of Billionnet and Soutif. Reoptimization technics are used to reduce importantly (up to 60%) the number of iterations in the linear knapsack resolutions done in both lagrangian methods.

Problèmes paradigmatiques , Optimisation Combinatoire, volume 4

The 0-1 quadratic knapsack problem consists in maximizing a quadratic function subject to a linear capacity constraint. To solve exactly this problem with a branch and bound algorithm, we need to obtain good lower an upper bounds in order to fix a lot of variables in the pre-treatment phase at the root node of the branch and bound tree if we want to solve large instances. We introduce reoptimization technics in this pre-treatment phase using the lagrangean relaxation of Caprara, Pisinger and Toth and the lagrangean decomposition of Billionnet and Soutif that give the best upper bounds known today. Reoptimization technics are used to reduce importantly (until 60%) the number of iterations in the linear knapsack resolutions done in both lagrangean methods.

26-28 février

Resume Les programmes fractionnaires concaves-convexes consistent en la maximisation d'un objectif rapport d'une fonction concave et une fonction convexe soumis a des contraintes convexes. Pour ces modeles a objectif non lineaire et non concave (non convexe), une nouvelle decomposition lagrangienne basee sur une reecriture fractionnaire des contraintes, est proposee. Elle combine la resolution d'un programme en variables 0 – 1 a objectif lineaire sous les contraintes initiales et celle d'un programme fractionnaire sans contraintes. Lorsque les contraintes sont lineaires, le resultat de dominance de la decomposition lagrangienne sur la relaxation lagrangienne est prouve.

Cet article est un travail de synthese autour de l'analyse de sensibilite pour les problemes lineaires en variables 0-1. De nombreux aspects sont ainsi abordes: historique et formes d'analyse de sensibilite, exemples d'application, complexite, conditions d'optimalite, algorithmes et approches. Nous dressons par ailleurs quelques perspectives de recherche actuelles dans ce domaine.

International audience; The 0-1 quadratic knapsack problem consists in maximizing a quadratic objective function subject to a linear capacity constraint. To solve exactly large instances of this problem with a tree search algorithm (e.g. a branch and bound method), the knowledge of good lower and upper bounds is crucial for pruning the tree but also for fixing as many variables as possible in a preprocessing phase. The upper bounds used in the best known exact approaches are based on Lagrangian relaxation and decomposition. It appears that the computation of these Lagrangian dual bounds involves the resolution of numerous 0-1 linear knapsack subproblems. Thus, taking this huge number of solvings into account, we propose to embed reoptimization techniques for improving the efficiency of the preprocessing phase of the 0-1 quadratic knapsack resolution. Namely, reoptimization is introduced to accelerate each independent sequence of 0-1 linear knapsack problems induced by the Lagrangian relaxation as well as the Lagrangian decomposition. Numerous numerical experiments validate the relevance of our approach.

International audience; 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 intensication 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.

International audience; This paper focuses on accelerating strategies in a Column Generation (CG) algorithm. In order to decrease the total number of generated columns and then, master problems resolution time, pricing problems solutions are made of task-disjoint columns. This can be achieved by diversification methods. Another way to improve CG computing time is to use reoptimization approaches to solve efficiently the pricing problems. We show in this work that diversification approaches are more efficient when applied on the first iterations to build efficiently a good approximation of pricing problems convex hull and that reoptimization methods are more efficient when applied on the last iterations when the dual variables are close. We combine a diversification technique and a reoptimization procedure in a CG scheme to improve the global resolution time. This study is validated on the Vehicle Routing Problem with Time Windows (VRPTW), defined on acyclic networks.