Retour au site du LAAS-CNRS

Laboratoire d’analyse et d’architecture des systèmes

Publications de l'équipe ROC

Choisir la langue : FR | EN

675documents trouvés

18024
18/02/2019

Long-term electric geostationary station-keeping via integer programming

C.GAZZINO, D.ARZELIER, C.LOUEMBET

MAC, ROC

Revue Scientifique : Journal of Guidance, Control, and Dynamics, Février 2019, doi10.2514/1.G003644 , N° 18024

Diffusable

Plus d'informations

Abstract

The problem of the computation of correction maneuvers for the fuel-optimal long-term station-keeping within a predefined longitude and latitude window of a geostationary satellite equipped with electric propulsion is investigated. The use of electric thrusters imposes some additional operational constraints on actuation that can be reformulated as logical constraints on the control function. The resulting fuel-optimal station-keeping problem is therefore transformed into a mixed linear integer programming problem. The long-term horizon of station-keeping is divided in shorter control cycles synchronized with the cycles of orbit determination, and the long-term station-keeping problem amounts to solve a sequence of similar mixed linear integer programming problems with different initial conditions. Two different terminal constraints on geographical positions and/or linear velocities are added to the formulation of the mixed linear integer programming problems to ease the feasibility of the whole sequence of successive resolutions. Nonlinear perturbed simulations of the computed control strategies show their efficiency on a long-term station-keeping problem lasting one year.

146604
18599
10/12/2018

Techniques d'optimisation pour la détection et ré-identification de personnes dans un réseau de caméras

FBARBOSA ANDA

RAP, ROC

Doctorat : Université de Toulouse III - Paul Sabatier, 10 Décembre 2018, 162p., Président: L.TAMINE-LECHANI, Rapporteurs: V.T'KINDT, J.M.M.C.PEREIRA BATISTA, Examinateurs: M.BABEL, Directeurs de thèse: C.BRIAND, F.LERASLE , N° 18599

Lien : https://hal.laas.fr/tel-02079969

Diffusable

Plus d'informations

Résumé

Cette thèse traite de la détection et de la ré-identification de personnes dans un environnement instrumenté par un réseau de caméras à champ disjoint. Elle est à la confluence des communautés Recherche Opérationnelle et Vision car elle s’appuie sur des techniques d’optimisation combinatoire pour formaliser de nouvelles modalités de vision par ordinateur. Dans ce contexte, un détecteur visuel de personnes, basé sur la programmation linéaire en nombres entiers, est tout d’abord proposé. Son originalité est de prendre en compte le coût de traitement et non uniquement les performances de détection. Ce détecteur est évalué et comparé aux détecteurs de la littérature les plus performants. Ces expérimentations menées sur deux bases de données publiques mettent clairement en évidence l’intérêt de notre détecteur en terme de coût de traitement avec garantie de performance de détection. La seconde partie de la thèse porte sur la modalité de ré-identification de personnes. L’originalité de notre approche, dénommée D-NCR (pour Directed Network Consistent Re-identification), est de prendre explicitement en compte les temps minimum de transit des personnes dans le réseau de caméras et sa topologie pour améliorer la performance de la ré-identification. On montre que ce problème s’apparente à une recherche de chemins disjoints particuliers à profit maximum dans un graphe orienté. Un programme linéaire en nombres entiers est proposé pour sa modélisation et résolution. Les évaluations réalisées sur une base publique d’images sont prometteuses et montrent le potentiel de cette approche.

Mots-Clés / Keywords
Optimisation combinatoire; Détection de personnes; Réidentification de personnes;

146893
18586
06/12/2018

Planification et ordonnancement de projets sous contraintes de ressources complexes

P.MORIN

ROC

Doctorat : Université de Toulouse III - Paul Sabatier, 6 Décembre 2018, 140p., Président: J.C.BILLAUT, Rapporteurs: S.DEMASSEY, N.TRAUTMANN, Examinateurs: C.BRIAND, F.CLAUTIAUX, Directeurs de thèse: A.HAIT, C.ARTIGUES , N° 18586

Lien : https://hal.laas.fr/tel-02053199

Diffusable

Plus d'informations

Abstract

The project structure arises in many fields of industry and services. It consists in performing a set of activities that may be linked by precedence relations, and use resources whose capacity is limited. The objective is to minimize a criterion usually linked to the duration or the cost of the project. Most of project scheduling problems in the literature assume that the same time scale should be used to determine activity start and completion dates and check resource constraints at each time. However, although it is often required in practice to build a precise schedule specifying the execution range of each activity, the resource usage can be evaluated on an aggregated basis, like worker shifts. In this thesis, a new model that enables the integration of these two time scales is presented in order to define the periodically aggregated resource-constrained project scheduling problem (PARCPSP). This problem is studied within the framework of complexity theory and several structural properties are established, highlighting major differences with the standard resource-constrained project scheduling problem (RCPSP). These properties allow deriving exact formulations based on integer linear programming, whose linear relaxations are compared. Moreover, several heuristics, such as schedule generations schemes, or an approached method based on a multi time scale iterative process, are proposed. Experimental results show the interest of these different methods and point out the intractability of the problem.

Résumé

La structure de projet se retrouve dans de nombreux contextes de l’industrie et des services. Il s’agit de réaliser un ensemble d’activités pouvant être connectées par des liens logiques de séquence (antériorité), en faisant appel à des ressources disponibles en quantité limitée. L’objectif est la minimisation d’un critère généralement lié à la durée ou au coût du projet. La plupart des problèmes d’ordonnancement de projet dans la littérature considèrent une unité de temps commune pour la détermination des dates d’exécution des activités et pour l’évaluation instantanée du respect des capacités des ressources qu’elles utilisent. Or, s’il est souvent nécessaire en pratique d’obtenir un calendrier détaillé des plages d’exécution des activités, l’utilisation des ressources peut être évaluée sur un horizon plus agrégé, comme par exemple les quarts de travail des employés. Dans cette thèse, un nouveau modèle intégrant ces deux échelles de temps est présenté afin de définir le problème d’ordonnancement de projet avec agrégation périodique des contraintes de ressources (PARCPSP). Ce problème est étudié du point de vue de la théorie de la complexité et des propriétés structurelles sont établies, mettant notamment en évidence des différences majeures avec le problème classique d’ordonnancement de projet sous contraintes de ressources (RCPSP). De ces propriétés sont dérivées des formulations exactes basées sur la programmation linéaire en nombres entiers, comparées en termes de qualité de la relaxation linéaire. Par ailleurs, plusieurs heuristiques, telles que des algorithmes de liste, ou une méthode approchée basée sur une résolution itérative qui exploite différentes échelles de temps, sont proposées. Les résultats expérimentaux montrent l’intérêt de ces différentes méthodes et illustrent la difficulté du problème.

Mots-Clés / Keywords
Planification; Ordonnancement; Projet; Optimisation combinatoire; Programmation linéaire en nombres entiers; Planning; Scheduling; Project; Combinatorial optimization; Integer linear programming;

146755
18414
03/12/2018

Méthodes d'optimisation robuste pour les problèmes d'ordonnancement cyclique

I.HAMAZ

ROC

Doctorat : Université de Toulouse III - Paul Sabatier, 3 Décembre 2018, 148p., Président: A.ROSSI, Rapporteurs: P.CHRETIENNE, M.POSS, Examinateurs: C.ARTIGUES, Directeurs de thèse: L.HOUSSIN, S.CAFIERI , N° 18414

Lien : https://hal.laas.fr/tel-01975512

Diffusable

Plus d'informations

Abstract

Several studies on cyclic scheduling problems have been presented in the literature. However, most of them consider that the problem parameters are deterministic and do not consider possible uncertainties on these parameters. However, the best solution for a deterministic problem can quickly become the worst one in the presence of uncertainties, involving bad schedules or infeasibilities. Many sources of uncertainty can be encountered in scheduling problems, for example, activity durations can decrease or increase, machines can break down, new activities can be incorporated, etc. In this PhD thesis, we focus on scheduling problems that are cyclic and where activity durations are affected by ("the" a effacer) uncertainties. More precisely, we consider an uncertainty set where each task duration belongs to an interval, and the number of parameters that can deviate from their nominal values is bounded by a parameter called budget of uncertainty. This parameter allows us to control the degree of conservatism of the resulting schedule. In particular, we study two cyclic scheduling problems. The first one is the basic cyclic scheduling problem (BCSP). We formulate the problem as a two-stage robust optimization problem and, using the properties of this formulation, we propose three algorithms to solve it. The second considered problem is the cyclic jobshop problem (CJSP). As for the BCSP, we formulate the problem as two-stage robust optimization problem and by exploiting the algorithms proposed for the robust BCSP we propose a Branch-and-Bound algorithm to solve it. In order to evaluate the efficiency of our method, we compared it with classical decomposition methods for two-stage robust optimization problems that exist in the literature. We also studied a version of the CJSP where each task duration takes uniformly values within an interval and where the objective is to minimize the mean value of the cycle time. In order to solve the problem, we adapted the Branch-and-Bound algorithm where in each node of the search tree, the problem to be solved is the computation of a volume of a polytope. Numerical experiments assess the efficiency of the proposed methods.

Résumé

Plusieurs problèmes d’ordonnancement cyclique ont été étudiés dans la littérature. Cependant, la plupart de ces travaux considèrent que les paramètres sont connus avec certitude et ne prennent pas en compte les différents aléas qui peuvent survenir. Par ailleurs, un ordonnancement optimal pour un problème déterministe peut très vite devenir le pire ordonnancement en présence d’incertitude. Parmi les incertitudes que nous pouvons rencontrer dans les problèmes d’ordonnancement, la variation des durées des tâches par rapport au valeurs estimées, pannes des machines, incorporation de nouvelles tâches qui ne sont pas considérées au départ, etc. Dans cette thèse, nous étudions des problèmes d’ordonnancement cyclique où les durées des tâches sont affectées par des incertitudes. Ces dernières sont décrites par un ensemble d’incertitude où les durées des tâches sont supposées appartenir à des intervalles et le nombre de déviations par rapport aux valeurs nominales est contrôlé par un paramètre appelé budget d’incertitude. Nous étudions deux problèmes en particulier. Le premier est le problème d’ordonnancement cyclique de base (BCSP). Nous formulons celui-ci comme un problème d’optimisation robuste bi-niveau et, à partir des propriétés de cette formulation, nous proposons différents algorithmes pour le résoudre. Le deuxième problème considéré est le problème du jobshop cyclique. De manière similaire au BSCP, nous proposons une formulation en termes de problème d’optimisation bi-niveau et, en exploitant les algorithmes développés pour le problème d’ordonnancement cyclique de base, nous développons un algorithme de Branch-and-Bound pour le résoudre. Afin d’évaluer l’efficacité de notre méthode nous l’avons comparé à des méthodes de décomposition qui existent dans la littérature pour ce type de problèmes. Enfin, nous avons étudié une version du problème du jobshop cyclique où les durées des tâches prennent des valeurs dans des intervalles d’une manière uniforme et dont l’objectif est de minimiser la valeur moyenne du temps de cycle. Pour résoudre ce problème nous avons adopté un algorithme de Branch-and-Bound où chaque sous-problème de l’arbre de recherche consiste à calculer le volume d’un polytope. Enfin, pour montrer l’efficacité de chacune de ses méthodes, des résultats numériques sont présentés.

Mots-Clés / Keywords
Ordonnancement cyclique; Optimisation robuste; Optimisation combinatoire; Cyclic scheduling; Robust optimization; Combinatorial optimization;

145533
18538
01/12/2018

Robust Static Output Feedback Design with Deterministic and Probabilistic Certificates

D.ARZELIER, F.DABBENE, S.FORMENTIN, D.PEAUCELLE, L.ZACCARIAN

ROC, CNR-IEIIT, Torino, Politecnico, MAC

Ouvrage (contribution) : Uncertainty in Networked Systems, Springer, N°ISBN 978-3-030-04629-3, Décembre 2018, pp.121-148 , N° 18538

Lien : https://hal.laas.fr/hal-01970884

Diffusable

Plus d'informations

Abstract

Static output feedback design for linear plants is well known to be a challenging non-convex problem. The presence of plant uncertainty makes this challenge even harder. In this chapter, we propose a new BMI formulation with S-variables which includes an interesting link between state feedback, output injection , state injection and static output feedback gains in a unified framework. Based on this formulation, the robust design problem is suitably addressed by iterative optimization procedures with either deterministic or probabilistic viewpoints exploiting the fact that Lyapunov certificates are separated from the control gain design variables. The deterministic approach is for affine polytopic systems. The proba-bilistic approach requires no assumption on the uncertain system and is based on the Scenario with Certificates (SwC) method which was recently proposed to address certain static anti-windup design problems. Numerical results illustrate the effectiveness of the approach in both deterministic and stochastic cases.

146393
18338
06/11/2018

Optimizing ground station networks for free space optical communications: maximizing the data transfer

M.CAPELLE, M.J.HUGUET, N.JOZEFOWIEZ, X.OLIVE

ROC, LCOMS, Thalès Alenia Space

Revue Scientifique : Networks, Vol.73, N°2, p.234-253, Novembre 2018, DOI : 10.1002/net.21859 , N° 18338

Lien : https://hal.laas.fr/hal-01898054

Diffusable

Plus d'informations

Abstract

Free space optical communications are becoming a mature technology to cope with the needs of high data rate payloads for future low‐earth orbiting observation satellites. However, they are strongly impacted by clouds. In this paper, we aim to find a network of optical ground stations maximizing the percentage of data acquired by a low‐earth orbiting satellite that can be transferred to the Earth, taking into consideration cloud information. This problem can be separated in two parts and solved hierarchically: the selection of a network of optical ground stations and the assignment of downloads to visibility windows of the stations. We present theoretical and practical results regarding the complexity of the latter subproblem and propose a dynamic programming algorithm to solve it. We combine this algorithm with two methods for the enumeration of the stations, and compare them with a mixed integer linear program (MILP). Results show that even if the MILP can solve scenarios over small horizons, the hierarchical approaches outperform it in term of computation time while still achieving optimality for larger instances.

144992
18339
06/11/2018

Energy management optimization of a smart wind power plant comparing heuristic and linear programming methods

R.BOURBON, S.U.NGUEVEU , X.ROBOAM, B.SARENI, C.TURPIN, D.HERNANDEZ-TORRES

LAPLACE, ROC

Revue Scientifique : Mathematics and Computers in Simulation, Vol.158, pp.418-431, Novembre 2018, doi 10.1016/j.matcom.2018.09.022 , N° 18339

Lien : https://hal.laas.fr/hal-01904983

Diffusable

Plus d'informations

Abstract

This paper aims at optimizing the energy management of a smart power plant composed of wind turbines coupled with a Lithium Ion storage device in order to fulfill a power production commitment to the utility grid. The application of this case study is typically related to islanded electric grids. Our work particularly investigates and compares two classes of energy management strategies for design purpose: a first capable of providing the global optimum of the power flow planning from a Linear Programming (LP) approach thanks to a priori knowledge of future events in the environment; a second, based on a classical control heuristic without any a priori knowledge on the future, applicable in real time. Beyond the future objectives in terms of system design (techno-economical sizing optimization), the comparison of both approaches also aims at improving the predefined heuristic from the analysis of the ideal reference provided by the global LP optimizer. In this scope, a linear power flow model of the power plant is developed in compliance with a LP solver (Cplex). A particular attention is paid to the techno-economic optimization including storage cost evaluation, commitment failure penalties and exploitation gains. Simulations and optimizations are carried out over one year in order to take variability and seasonal features of the wind potential into account.

144994
18543
01/11/2018

Piecewise linear bounding of univariate nonlinear functions and resulting mixed integer linear programming-based solution methods

S.U.NGUEVEU

ROC

Revue Scientifique : European Journal of Operational Research, Novembre 2018 , N° 18543

Lien : https://hal.archives-ouvertes.fr/hal-01444317

Diffusable

Plus d'informations

Abstract

Various optimization problems result from the introduction of nonlinear terms into combinatorial optimization problems. In the context of energy optimization for example, energy sources can have very different characteristics in terms of power range and energy demand/cost function, also known as efficiency function or energy conversion function. Introducing these energy sources characteristics in combinatorial optimization problems, such as energy resource allocation problems or energy-consuming activity scheduling problems may result into mixed integer nonlinear problems neither convex nor concave. Approximations via piecewise linear functions have been proposed in the literature. Non-convex optimization models and heuristics exist to compute optimal breakpoint positions under a bounded absolute error-tolerance. We present an alternative solution method based on the upper and lower bounding of nonlinear terms using non necessarily continuous piecewise linear functions with a relative epsilon-tolerance. Conditions under which such approach yields a pair of mixed integer linear programs with a performance guarantee are analyzed. Models and algorithms to compute the non necessarily continuous piecewise linear functions with absolute and relative tolerances are also presented. Computational evaluations performed on energy optimization problems for hybrid electric vehicles show the efficiency of the method with regards to the state of the art.

146403
18311
18/10/2018

Trains do not vanish: the ROADEF/EURO challenge 2014

C.ARTIGUES, E.BOURREAU, V.JOST, S.KEDAD SIDHOUM, F.RAMOND

ROC, LIRMM, UGA, LIP6-CNRS, SNCF

Revue Scientifique : Annals of Operations Research, Vol.271, N°2, pp.1091-1105, Octobre 2018 , N° 18311

Lien : https://hal.laas.fr/hal-01883062

Diffusable

Plus d'informations

Abstract

The ROADEF/EURO challenge is a contest jointly organized by the French Operational Research and Decision Aid society (ROADEF) and the European Operational Research society (EURO). The contest has appeared on a regular basis since 1999 and always concerns an applied optimization problem proposed by an industrial partner. The 2014 edition of the ROADEF/EURO challenge was led by the Innovation & Research department of SNCF, a global leader in passenger and freight transport services, and infrastructure manager of the French railway network. The objective of the challenge was to find the best way to store and move trains on large railway sites, between their arrivals and departures. Since trains never vanish and traffic continues to increase, in recent years some stations have been having real congestion issues. Train management in large railway sites is of high interest for SNCF, which is why it was submitted to the operations research community as the industrial problem for the 2014 edition of the ROADEF/EURO challenge. This paper introduces the special section of the Annals of Operations Research volume devoted to the ROADEF/EURO challenge 2014, as well as the methods of the finalist teams and their results.

144794
18214
05/10/2018

Fuel-optimal impulsive fixed-time trajectories in the linearized circular restricted 3-body-problem

R.SERRA , D.ARZELIER, F.BREHARD, M.M.JOLDES

MAC, ROC

Manifestation avec acte : International Astronautical Congress ( IAC ) 2018 du 01 octobre au 05 octobre 2018, Breme (Allemagne), Octobre 2018, 9p. , N° 18214

Lien : https://hal.archives-ouvertes.fr/hal-01830253

Diffusable

Plus d'informations

Abstract

The problem of fixed-time fuel-optimal trajectories with high-thrust propulsion in the vicinity of a Lagrange point is tackled via the linear version of the primer vector theory. More precisely, the proximity to a Lagrange point i.e. any equilibrium point-stable or not-in the circular restricted three-body problem allows for a linearization of the dynamics. Furthermore, it is assumed that the spacecraft has ungimbaled thrusters, leading to a formulation of the cost function with the 1-norm for space coordinates, even though a generalization exists for steerable thrust and the 2-norm. In this context, the primer vector theory gives necessary and sufficient optimality conditions for admissible solutions to two-value boundary problems. Similarly to the case of rendezvous in the restricted two-body problem, the in-plane and out-of-plane trajectories being uncoupled, they can be treated independently. As a matter of fact, the out-of-plane dynamics is simple enough for the optimal control problem to be solved analytically via this indirect approach. As for the in-plane dynamics, the primer vector solution of the so-called primal problem is derived by solving a hierarchy of linear programs, as proposed recently for the aforementioned rendezvous. The optimal thrusting strategy is then numerically obtained from the necessary and sufficient conditions. Finally, in-plane and out-of-plane control laws are combined to form the complete 3-D fuel-optimal solution. Results are compared to the direct approach that consists in working on a discrete set of times in order to perform optimization in finite dimension. Examples are provided near various Lagrange points in the Sun-Earth and Earth-Moon systems, hinting at the extensive span of possible applications of this technique in station-keeping as well as mission analysis, for instance when connecting manifolds to achieve escape or capture.

144218
Les informations recueillies font l’objet d’un traitement informatique destiné à des statistiques d'utilisation du formulaire de recherche dans la base de données des publications scientifiques. Les destinataires des données sont : le service de documentation du LAAS.Conformément à la loi « informatique et libertés » du 6 janvier 1978 modifiée en 2004, vous bénéficiez d’un droit d’accès et de rectification aux informations qui vous concernent, que vous pouvez exercer en vous adressant à
Pour recevoir une copie des documents, contacter doc@laas.fr en mentionnant le n° de rapport LAAS et votre adresse postale. Signalez tout problème de dysfonctionnement à sysadmin@laas.fr. http://www.laas.fr/pulman/pulman-isens/web/app.php/