Teses / dissertações sobre o tema "Méthodes de relaxation (Mathématiques)"
Crie uma referência precisa em APA, MLA, Chicago, Harvard, e outros estilos
Veja os 50 melhores trabalhos (teses / dissertações) para estudos sobre o assunto "Méthodes de relaxation (Mathématiques)".
Ao lado de cada fonte na lista de referências, há um botão "Adicionar à bibliografia". Clique e geraremos automaticamente a citação bibliográfica do trabalho escolhido no estilo de citação de que você precisa: APA, MLA, Harvard, Chicago, Vancouver, etc.
Você também pode baixar o texto completo da publicação científica em formato .pdf e ler o resumo do trabalho online se estiver presente nos metadados.
Veja as teses / dissertações das mais diversas áreas científicas e compile uma bibliografia correta.
Liess, Olivier. "Méthodes de décomposition non standard et applications". Avignon, 2006. http://www.theses.fr/2006AVIG0145.
Texto completo da fonteNeto, José. "Développement d'algorithmes de génération de contraintes et extensions". Evry, Institut national des télécommunications, 2006. http://www.theses.fr/2006TELE0003.
Texto completo da fonteSince they first appeared in the 50's, contraint generation algorithms are now commonly used when solving hard problems through a linear programming approach. In these algorithms, a relaxation of the formulation containing only a subset of the constraints is first solved. Then a separation procedure is called which adds to the relaxation any inequality of the formulation that is violated by the current solution. The process is iterated until no violated inequality can be found. We propose a modification of this resolution scheme at the level of the separation point used in order to improve performance. More precisely, we introduce two approaches. The first one, entitled In/Out, consists in defining the separation point as a convex combination of an optimal solution for the current relaxation, and of a feasible solution. Numerical experiments have been carried out on different problem types : randomly generated linear programs, survivability network design and multicommodity min-cost flow problems, namely. They show evidence of a potential strong improvement of performances with this kind of procedures. Another developed approach consists in using several points in the separation phase. We study the complexity of this kind of separation generalizing classical procedures, and of some other related problems. Namely we establish polynomial equivalence between a classical single-point separation and the multiple-points separation proposed. Preliminary computational experiments for this kind of separation illustrate efficiency of this approach. Both introduced methods : In/Out and multiple-points essentially differ from classical constraint generation procedures at the level of the point being used for separation. Another way to improve traditional schemes would consist in modifying the separation oracle so as to favour the generation of some particular inequalities. In this thesis we give a general characterization of relaxations with the same set of optimal solution as the one for the original problem, thus leading to an evaluation of the “relevance” of constraints present in the formulation used to get an optimal solution. Finally we report investigations on the maximum cut problem, at two levels. First we establish polynomiality of the separation problem for generalizations of two families of inequalities for some fixed parameter values : the so-called suspended-tree and path-block-cycle inequalities. Then, we introduce and evaluate an original rouding procedure applied to a particular formulation of the problem through a divide-and-conquer approach
Touati, Nora. "Amélioration des performances du schéma de la génération de colonnes : application aux problèmes de tournées de véhicules". Paris 13, 2008. http://www.theses.fr/2008PA132032.
Texto completo da fonteColumgeneration algorithms are instrumental in many areas of applied optimization where linear programs with an enormous number of variables need to be solued. Although success fully used in many applications, this method suffers from well-known "instability" issues, that somewhat limit its efficiency. This work focuses on accelerating strategies in a column generation algorithm. We propose some diversifiication methods in order to decrease the total number of generated columns and then master problems resolution time. We interest also to solving efficiently the pricing problems, by proposing an improning approch based on reoptimization principle and a new variant of the dynamic programming algorithm. The effectiveness of these approches is validated on vehicule routing problem with time windows
Fei, Hongying. "Vers un outil d'aide à la planification et à l'ordonnancement des blocs opératoires". Troyes, 2006. http://www.theses.fr/2006TROY0004.
Texto completo da fonteThis thesis presents our studies on the operating theatre management, especially on the operating theatre planning and scheduling problem in case that this surgical sector is always regarded as the kernel in a hospital in terms of the expenditure. Therefore, it’s necessary to optimize the assignment of hospital resources in the operating theatre. Since this type of problem is extremely complex, we concentrate on just two sub-problems that are also considered difficult ones by researchers: the surgical cases planning and scheduling problem, which aim to made a surgical cases programming with an objective of obtaining a realizable and efficient surgical cases operating schedule. At firth the weekly planning problems of surgical cases are formulated as a mathematical integer programming, and then they are solved by heuristic procedures and Branch-and-Price ones. All these procedures are based on the column generation procedure, which is used to solve the linear relaxation of each model for a lower bound. The scheduling models are treated as variants of hybrid two-stage flow shop problem and are solved by proposed hybrid genetic algorithms. Finally, our models are tested and validated in a real case
Loiseau, Irène. "Sur la génération de colonnes en nombres entiers". Paris 13, 2005. http://www.theses.fr/2005PA132018.
Texto completo da fonteWorrakitpoonpon, Tirawut. "Relaxation of isolated self-gravitating systems in one and three dimensions". Paris 6, 2011. http://www.theses.fr/2011PA066190.
Texto completo da fonteLargeron, Christine. "Reconnaissance de formes par relaxation : un modèle d'aide à la décision". Lyon 1, 1990. http://www.theses.fr/1990LYO10256.
Texto completo da fonteEttaouil, Mohamed. "Satisfaction de contraintes non linéaires en variables 0-1 et outils de la programmation quadratique". Paris 13, 1994. http://www.theses.fr/1994PA132006.
Texto completo da fonteBordes, Laurent. "Inférence statistique pour des modèles paramétriques et semi-paramétriques : modèles de l'exponentielle multiple, test du Chi-deux, modèles de vie accélérée". Bordeaux 1, 1996. http://www.theses.fr/1996BOR10649.
Texto completo da fonteMartin, Véronique. "Méthodes de décomposition de domaine de type relaxation d'ondes pour des équations de l'océanographie". Phd thesis, Université Paris-Nord - Paris XIII, 2003. http://tel.archives-ouvertes.fr/tel-00583196.
Texto completo da fonteDiop, Mouhamed el Moctar. "Planification et conception topologique des réseaux de télécommunications cellulaires". Clermont-Ferrand 2, 2005. http://195.221.120.247/simclient/consultation/binaries/stream.asp?INSTANCE=UCFRSIM&eidmpa=DOCUMENTS_THESES_83.
Texto completo da fonteSaleh, Khaled. "Analyse et simulation numérique par relaxation d'écoulements diphasiques compressibles : contribution au traitement des phases évanescentes". Paris 6, 2012. https://theses.hal.science/tel-00761099.
Texto completo da fonteThis thesis deals with the Baer-Nunziato two-phase flow model. The main objective of this work is to propose some techniques to cope with phase vanishing regimes which produce important instabilities in the model and its numerical simulations. Through analysis and simulation methods using Suliciu relaxation approximations, we prove that in these regimes, the solutions can be stabilised by introducing some extra dissipation of the total mixture entropy. In a first approach, called the Eulerian approach, the exact resolution of the relaxation Riemann problem provides an accurate entropy-satisfying numerical scheme, which turns out to be much more efficient in terms of CPU-cost than the classical and very simple Rusanov's scheme. Moreover, the scheme is proved to handle the vanishing phase regimes with great stability. The scheme, first developed in 1D, is then extended in 3D and implemented in an industrial code developed by EDF. The second approach, called the acoustic splitting approach, considers a separation of fast acoustic waves from slow material waves. The objective is to avoid the resonance due to the interaction between these two types of waves, and to allow an implicit treatment of the acoustics, while material waves are explicitly discretized. The resulting scheme is very simple and allows to deal simply with phase vanishing. The originality of this work is to use new dissipative closure laws for the interfacial velocity and pressure, in order to control the solutions of the Riemann problem associated with the acoustic step, in the phase vanishing regimes
Chouai, Sihem. "Calcul tridimensionnel des champs électromagnétiques dans les applicateurs par la méthode de relaxation". Toulouse, INPT, 1998. http://www.theses.fr/1998INPT022H.
Texto completo da fonteCherfi, Nawal. "Méthodes de résolution hybrides pour les problèmes de type knapsack". Paris 1, 2008. http://www.theses.fr/2008PA010056.
Texto completo da fonteDrullion, Frédérique. "Définition et étude de systèmes linéaires pour la simulation d'écoulements et l'optimisation de formes aérodynamiques par méthode de gradient". Bordeaux 1, 2004. http://www.theses.fr/2004BOR12898.
Texto completo da fonteGomes, Cristiana Maria Nascimento. "Radio mesh networks and the round weighting problem". Nice, 2009. http://www.theses.fr/2009NICE4049.
Texto completo da fonteIn this thesis, we address the joint routing and slot assignment problem in radio mesh access networks between the routers and the gateways. We model the problem as a Round Weighting Problem (RWP) in which the objective is to minimize the overall period of slot activations providing enough capacity to satisfy the bandwidth requirements of the routers. Solving the full problem means generating an exponential set of simultaneous transmission rounds which is intractable even for small networks. To cope with this issue, we implement a mathematical multi-objective model to solve the problem using a column generation method. We observe that the bottleneck is usually located in a limited region around a gateway. We propose a method to obtain lower bounds (considering only a limited probable bottleneck region) and upper bounds for general graphs. Our methods are applied to grid graphs providing closed formulae for the case of uniform demands, and also optimal routing strategies considering non-uniform demands. Motivated by the results of the existence of a limited (bottleneck) region capable of representing the whole network, we consider a variant of the RWP dealing also with bandwidth allocation, but considering SINR conditions in a CDMA network. We give sufficient conditions for the whole network to be reduced to a single-hop around the gateway. It is due to the fact that the problem is convex under some conditions that are often met. We are interested in Pareto-optimal solutions in which each flow going through a bottleneck receives a fair share of the available bandwidth
Mellouli, Racem. "Ordonnancement sur machines parallèles avec contraintes d'indisponibilité". Troyes, 2007. http://www.theses.fr/2007TROY0022.
Texto completo da fonteThis thesis is devoted to parallel machine scheduling with availability constraints for minimizing the flow time. We studied three theoretical models of this problem. The objective is to propose theoretical optimization methods that effectively solve these problems. We develop various approaches. Indeed, we proposed heuristic methods that improved classical methods from literature. Three types of exact approaches were considered : methods based on mixes integer linear programming, branch-and-bound methods using different branching schemes and methods based on dynamic programming. We also proposed constructive and iterative lower bounding schemes. In particular, lower bounds based on Lagrangian relaxation are combined with different tools from operational research, such as the subgradient method, dynamic programming and job splitting. Moreover, a method based on column generation has been developed based on a particular formulation of the problem. Auxiliary problems are solves with a heuristic method and an exact method using the dynamic programming. Furthermore, we proved several mathematical properties and proposed new lower bounds for a model already studied in the literature. Finally, we have studied worst-case performance for simple heuristics and a lower bound
MOULET, DOMINIQUE. "Extraction et suivi de contours dans les sequences d'images animees". Nantes, 1990. http://www.theses.fr/1990NANT2016.
Texto completo da fonteNardi, Giacomo. "On a characterization of the relaxation of a generalized Willmore functional". Paris 6, 2011. http://www.theses.fr/2011PA066539.
Texto completo da fonteLabois, Mathieu. "Modélisation des déséquilibres mécaniques dans les écoulements diphasiques : approches par relaxation et par modèle réduit". Aix-Marseille 1, 2008. http://www.theses.fr/2008AIX11039.
Texto completo da fonteThis thesis deals with hyperbolic models for the simulation of compressible two-phase flows, to find alternatives to the classical bifluid model. We first establish a hierarchy of two-phase flow models, obtained according to equilibrium hypothesis between the physical variables of each phase. The use of Chapman-Enskog expansions enables us to link the different existing models to each other. Moreover, models that take into account small physical unbalances are obtained by means of expansion to the order one. The second part of this thesis focuses on the simulation of flows featuring velocity unbalances and pressure balances, in two different ways. First, a two-velocity two-pressure model is used, where non-instantaneous velocity and pressure relaxations are applied so that a balancing of these variables is obtained. A new one-velocity one-pressure dissipative model is then proposed, where the arising of second-order terms enables us to take into account unbalances between the phase velocities. We develop a numerical method based on a fractional step approach for this model
Arada, Nadir. "Contrôle optimal d'équations paraboliques avec contraintes sur l'état : relaxation et stabilité". Toulouse 3, 1997. http://www.theses.fr/1997TOU30101.
Texto completo da fonteDetienne, Boris. "Planification et ordonnancement : méthodes de décomposition et génération de coupes". Compiègne, 2007. http://www.theses.fr/2007COMP1683.
Texto completo da fonteThis PhD thesis consists in the study of two problems in Operational Research. In the first part, a lagrangian lower bound is proposed for a particular employee timetabling problem, followed by a Benders decomposition and a specific cut generation process based on an exponential formulation, that allow the solving of real-size instances. For solving bigger instances, a taboo method is developed. The second part is a study of the Single Machine Earliness- Tardiness Problem with general completion costs and release dates. After computational results obtained by different lower bounds, we give several dominance rules, and provide new elimination rules that turn out to be very efficient. Indeed, we develop an exact method dominating all known approaches for this problem
Mechti, Redouane. "Contribution à la résolution des problèmes de tournées de véhicules avec fenêtres de temps et composition de flotte". Versailles-St Quentin en Yvelines, 1999. http://www.theses.fr/1999VERS0023.
Texto completo da fonteBerthe, Paul-Marie. "Méthodes de décomposition de domaine de type relaxation d'ondes optimisées pour l'équation de convection-diffusion instationnaire discrétisée par volumes finis". Thesis, Paris 13, 2013. http://www.theses.fr/2013PA132055.
Texto completo da fonteIn the context of nuclear waste repositories, we consider the numerical discretization of the non stationary convection diffusion equation. Discontinuous physical parameters and heterogeneous space and time scales lead us to use different space and time discretizations in different parts of the domain. In this work, we choose the discrete duality finite volume (DDFV) scheme and the discontinuous Galerkin scheme in time, coupled by an optimized Scwharz waveform relaxation (OSWR) domain decomposition method, because this allows the use of non-conforming space-time meshes. The main difficulty lies in finding an upwind discretization of the convective flux which remains local to a sub-domain and such that the multidomain scheme is equivalent to the monodomain one. These difficulties are first dealt with in the one-dimensional context, where different discretizations are studied. The chosen scheme introduces a hybrid unknown on the cell interfaces. The idea of upwinding with respect to this hybrid unknown is extended to the DDFV scheme in the two-dimensional setting. The well-posedness of the scheme and of an equivalent multidomain scheme is shown. The latter is solved by an OSWR algorithm, the convergence of which is proved. The optimized parameters in the Robin transmission conditions are obtained by studying the continuous or discrete convergence rates. Several test-cases, one of which inspired by nuclear waste repositories, illustrate these results
Le, Hai Yen. "Approche variationnelle de la fonction rang : relaxation convexe, sous-différentiation généralisée, régularisation-approximation de Moreau". Toulouse 3, 2013. http://thesesups.ups-tlse.fr/1973/.
Texto completo da fonteIn this dissertation, we consider the rank function from the variational point of view. The reason why we are interested in this function is that it appears as an objective (or constraint) function in various modern optimization problems, such as: low rank matrix completion, multivariate statistical data analysis, compressed sensing, etc. In some particular cases, the rank minimization problems can be solved by using the singular value decomposition of matrices or can be reduced to the solution of linear systems. But in general, the rank minimization problems is known to be « NP-hard ». We provide here several properties of the rank function from the variational point of view: additional proofs for its closed convex relaxation, the expressions of its generalized subdifferentials and the explicit expression of its Moreau regularization-approximation form. Then, in the last chapter, we revisit a notion whose definition resembles that of the rank, the cp-rank function
Zhang, Hanyu. "Méthodes itératives à retard pour architecture massivement parallèles". Thesis, Université Paris-Saclay (ComUE), 2016. http://www.theses.fr/2016SACLC068.
Texto completo da fonteWith the increase of architectures composed of multi-cores, many algorithms need to revisited and be modified to exploit the power of these new architectures. These algorithms divide the original problem into “small pieces” and distribute these pieces to different processors at disposal, thus communications among them are indispensible to assure the convergence. My thesis mainly focus on solving large sparse systems of linear equations in parallel with new methods. These methods are based on the gradient methods. Two key parameters of the gradient methods are descent direction and step-length of descent for each iteration. Our methods compute the directions locally, which requires less synchronization and computation, leading to faster iterations and make easy asynchronization possible. Convergence can be proved in both synchronized or asynchronized cases. Numerical tests demonstrate the efficiency of these methods. The other part of my thesis deal with the acceleration of the vector sequences generated by classical iterative algorithms. Though general chaotic sequences may not be accelerated, it is possible to prove that with any fixed retard pattern, then the generated sequence can be accelerated. Different numerical tests demonstrate its efficiency
Servigne, Sylvie. "Base de données géographiques et photos aériennes : de l'appariement à la mise à jour". Lyon, INSA, 1993. http://www.theses.fr/1993ISAL0026.
Texto completo da fontePresently, to update rapidly geographic databases is a problem. A methodology is presented to automatise the detection of change and the updating of cadastral informations by mean of aerial photos. After the analysis of the aerial specificities, we deal with the matching problem between geographic data (in particularly building) and information coming from image processing on aerial photos. Our work is divided into two parts because of data evolution, produced by the image processing process : - firstly, a labelling method is proposed based on relaxation to match contour segments of geographical objects with segments issued from the segmentation process ; - secondly, a matching method is defined between geographic and pictorial objects (areas of uniform texture from aerial photos) in order to detect changes. We then present an analysis of the interesting information which can help the interpretation of new objects (do not exist in the geographic database). Finally, some elements are given in order to design on operative system for updating geographic databases by means of serial photos
Cocquebert, Cédric. "Méthodes de type "Waveform-FAC" pour la résolution numérique de problèmes paraboliques". Aix-Marseille 1, 1997. http://www.theses.fr/1997AIX11032.
Texto completo da fonteChehab, Jean-Paul. "Méthode des inconnues incrémentales : application au calcul des bifurcations". Paris 11, 1993. http://www.theses.fr/1993PA112031.
Texto completo da fonteSolay, Rakotonirainy Georges. "Un coup d'œil non standard sur un problème de Zermelo". Nice, 1986. http://www.theses.fr/1986NICE4080.
Texto completo da fonteWang, Guanglei. "Relaxations in mixed-integer quadratically constrained programming and robust programming". Electronic Thesis or Diss., Evry, Institut national des télécommunications, 2016. http://www.theses.fr/2016TELE0026.
Texto completo da fonteMany real life problems are characterized by making decisions with current information to achieve certain objectives. Mathematical programming has been developed as a successful tool to model and solve a wide range of such problems. However, many seemingly easy problems remain challenging. And some easy problems such as linear programs can be difficult in the face of uncertainty. Motivated by a telecommunication problem where assignment decisions have to be made such that the cloud virtual machines are assigned to servers in a minimum-cost way, we employ several mathematical programming tools to solve the problem efficiently and develop new tools for general theoretical problems. In brief, our work can be summarized as follows. We provide an exact formulation and several reformulations on the cloud virtual machine assignment problem. Then several valid inequalities are used to strengthen the exact formulation, thereby accelerating the solution procedure significantly. In addition, an effective Lagrangian decomposition is proposed. We show that, the bounds providedby the proposed Lagrangian decomposition is strong, both theoretically and numerically. Finally, a symmetry-induced model is proposed which may reduce a large number of bilinear terms in some special cases. Motivated by the virtual machine assignment problem, we also investigate a couple of general methods on the approximation of convex and concave envelopes for bilinear optimization over a hypercube. We establish several theoretical connections between different techniques and prove the equivalence of two seeming different relaxed formulations. An interesting research direction is also discussed. To address issues of uncertainty, a novel paradigm on general linear problems with uncertain parameters are proposed. This paradigm, termed as multipolar robust optimization, generalizes notions of static robustness, affinely adjustable robustness, fully adjustable robustness and fills the gaps in-between. As consequences of this new paradigms, several known results are implied. Further, we prove that the multipolar approach can generate a sequence of upper bounds and a sequence of lower bounds at the same time and both sequences converge to the robust value of fully adjustable robust counterpart under some mild assumptions
Ngueveu, Sandra Ulrich. "Problèmes de tournées de véhicules avec contraintes particulières pour la maîtrise des risques". Troyes, 2009. http://www.theses.fr/2009TROY0013.
Texto completo da fonteThis research concerns solving two transportation problems that integrate constraints or objective-fonctions related to the risk management: the m-Peripatetic Vehicle Routing Problem (m-PVRP) and the Cumulative Capacitated Vehicle Routing Problem (CCVRP). Applications can be found in the security logistics field, such as money transportation, and the humanitarian logistics field, such as vital goods supply after a natural disaster. Most of our work is about the m-PVRP. It consists in finding a set of routes of minimal total cost over m periods such that each customer is served once per period and two customers are never sequenced consecutively during two different periods. Different mathematical models are presented and the problem complexity is discussed. Then, we propose polynomial lower bounds, two metaheuristics including a tabu search with diversification and guided by a b-matching solution, a column-generation-like approach combining dual heuristics with q-routes generation, and finally two branch-and-cut algorithms. The CCVRP consists in minimizing the sum of arrival times at customers, instead of the classical route cost or length, subject to the vehicle capacity. We propose a memetic algorithm (MA). Its efficiency lies upon the optimal splitting procedure of chromosomes without trip delimiters into feasible routes to obtain a feasible solution. Pre-computations to speed up MA and valid formulas to compute lower bounds are deduced from some CCVRP properties we identified. Up to now, this MA is the best metaheuristic published on the special case of the Traveling Repairman Problem ( = single-vehicle PTVCC = TRP
Mohite, Shivaraj. "Observer Design for Nonlinear Systems using LMI Relaxation Techniques". Electronic Thesis or Diss., Université de Lorraine, 2023. http://www.theses.fr/2023LORR0326.
Texto completo da fonteOver the last three decades, observer design for dynamical systems has emerged as a pivotal topic in the control system domain. This is a consequence of the fact that observers are used to collect real-time information about the systems, monitor the systems, control the system, and make decisions. The LMI-based observers have garnered considerable attention among the various established observer methodologies. The thesis predominantly deals with the design of the LMI-based observers for the Lipschitz nonlinear systems. One of the valuable contributions of this thesis is the establishment of more generalized matrix-multiplier-based LMIs. These LMI conditions are derived through the utilization of reformulated Lipschitz property, Young inequalities, and newly defined matrix multipliers. Further, an LMI-based H_∞ observer is designed to estimate the states of the nonlinear systems under the presence of disturbances/noise by using the previously defined matrix multipliers. The proposed LMIs contain additional numbers of decision variables as compared to the existing approaches, which add extra degrees of freedom thus improving their feasibility. The effectiveness of the developed approach is validated through numerical examples. This new matrix-multiplier-based LMI approach is extended for the state estimation for a class of non-globally Lipschitz nonlinear systems under the effect of noise/disturbances. It is achieved by deploying the Hilbert projection-based observer structure. The novel LMI condition is established to ensure the ISS behaviour of the state estimation error of the proposed observers. Furthermore, the proposed matrix-multiplier-based LMI approach is exploited for the stabilization of the disturbance-affected nonlinear systems using the observer-based controller. The judicious implementation of the matrix-multiplier-based LMIs made it possible to obtain less conservative LMI conditions than existing LMI methods in the literature. Finally, all these developed LMI-based observers are used in the autonomous vehicle area for various tasks, such as longitudinal state estimation, slip angle estimation, and so on to validate their performances
Garaix, Thierry. "Etude et résolution exacte de problèmes de transport à la demande avec qualité de service". Avignon, 2007. http://tel.archives-ouvertes.fr/docs/00/53/48/94/PDF/thesegaraix.pdf.
Texto completo da fonteIn this thesis, we address routing problems deriving from on-demand transport systems (ODT). Such systems, combining taxi flexibility with public transport system advantages (grouping, price) seem well suited to the new mobility needs. We define and classify a large set of quality of service criteria. We select three of them among the most representative : the total distance travelled, the vehicle occupancy rate and the passenger wasted-time. We propose branch-and-price solution schemes for the three cases, under the assumption that demands are known in advance. The original quality of service objectives introduce non-standard features into the vehicle routing model, namely a multigraph and a fractional objective function, therefore inducing non-standard algorithms. This work is part of a multidisciplinary project managed by geographers. The implementation of an operational ODT in the Doubs Central area (France) is used as a testing ground for experimentations. For the practical use of this system, we propose an insertion heuristic in addition to the branch-and-price algorithm. A geomatic analysis of the interactions between quality of service criteria and the geographical area is carried out with a Geographic Information System, with a special focus on route shapes and route sinuosity measures
Mancel, Catherine. "Modélisation et résolution de problèmes d'optimisation combinatoire issus d'applications spatiales". Toulouse, INSA, 2004. http://www.theses.fr/2004ISAT0011.
Texto completo da fonteIn this work we are concerned with combinatorial optimization problems stemming from space missions planning. These huge problems have some common features concerning the type of data, constraints and criteria to be optimized. We focus on linear programming for modeling and solving these problems, associated to methods for search space simplification, using decomposition or some constraint propagation techniques. We more particularly address two problems. The first one concerns a mission which aims at a scientific investigation of Mars. It consists in planning both communication slots between martian probes and a satellite, and experiments on probes. We use linear integer programming to model and solve to optimality the sub-problem of communication slots planning, and we develop an decision-aid oriented method using constraint propagation for experiments planning. The second problem occurs in the context of the french program of Earth observing with satellites. It consists in selecting and scheduling images taken by one satellite in order to maximize a quality criterion. We give a linear model and we propose a column generation approach, based on the Dantzig-Wolfe decomposition of the model, to calculate upper bounds for this problem and in order to solve it
Blondel, Oriane. "Dynamiques de particules sur réseaux avec contraintes cinétiques". Paris 7, 2013. http://www.theses.fr/2013PA077156.
Texto completo da fonteThis thesis is about stochastic lattice models of particle systems with Glauber dynamics and /kinetic constraints (KCSM), more specically the East and FA-1f models. These models were introduced in physics for the study of glassy systems. In this document one nds rst a summary of its contents (in French), then three introductory chapters in which I present the context of my works and show both what what my contributions add to the picture and on which notions and techniques they rely. In my presentation of KCSM, I focus on objects and results that are directly related to my research. Finally my papers are assembled in the Appendix, in some cases with extensions that were cut o for publication. The rst chapter is an introduction to KCSM. The second chapter presents non-equilibrium issues for KCSM. First I give results about out-of-equilibrium local relaxation; in the FA-1f mode it is a joint work with N. Cancrini, F. Martinelli, C. Roberto and C. Toninelli. Then I study the progression of a front in the East model and show a shape theorem as well as an ergodicity result for the process seen from the front. This result relies on quantifying the local relaxation of the process seen from the front rather than using classic sub-additivity arguments. The last chapter explores low-temperature (or high density) dynamics of KCSM. I rst recali asymptotic results about East and FA-1f spectral gaps and oer some heuristics and conjectures. I then focus on the low temperature behaviour of the diusion coecient of a tracer in a KCSM, so as to give rigorous answers to questions raised in the physics literature
Migot, Tangi. "Contributions aux méthodes numériques pour les problèmes de complémentarité et problèmes d'optimisation sous contraintes de complémentarité". Thesis, Rennes, INSA, 2017. http://www.theses.fr/2017ISAR0026/document.
Texto completo da fonteIn this thesis, we studied the regularization methods for the numerical resolution of problems with equilibria. In the first part, we focused on the complementarity problems through two applications that are the absolute value equation and the sparse optimization problem. In the second part, we concentrated on optimization problems with complementarity constraints. After studying the optimality conditions of this problem, we proposed a new regularization method, so-called butterfly relaxation. Then, based on an analysis of the regularized sub-problems we defined an algorithm with strong convergence property. Throughout the manuscript, we concentrated on the theoretical properties of the algorithms as well as their numerical applications. In the last part of this document, we presented numerical results using the regularization methods for the mathematical programs with complementarity constraints
Tran, Minh Binh. "La méthode de décomposition de domaines de Schwarz pour les problèmes linéaires et non-linéaires". Paris 13, 2011. http://www.theses.fr/2011PA132018.
Texto completo da fonteThe Schwarz domain decomposition methods are procedures to parallelize and solve partial differential equations numerically, in which each iteration involves the solutions of the original equations on smaller subdomains. Together with the development of domain decomposition methods, a theory of convergence for the methods is really needed and many efforts have been made in this direction; however, the problem still remains open, even for classical methods. In the first part of the thesis, we introduce a new method to solve the convergence problem of Schwarz methods. Our method works for parabolic and elliptic equations, linear and non-linear. In the second part, we apply our method to study the primitive equations and the forward-backward stochastic differential equations, where a new four-step domain decomposition scheme is introduced, based on the four-step scheme of Ma, Protter and Young. Optimized Schwar methods is a new class of Schwarz methods, which converges much faster than the classical ones, thanks to the improvement of the transmission conditions. In the third part of this thesis, we study this class of algorithms with Robin and second order transmission conditions for heat equation in 1 and 2 dimensions
Chabrier, Alain. "Génération de colonnes et de coupes utilisant des sous-problèmes de plus court chemin". Angers, 2003. http://www.theses.fr/2003ANGE0029.
Texto completo da fonteIn recent years, column generation methods have been the subject of many publications about solving a greater number of combinatorial optimisation pro-blems. They correspond to a particular use of the revised Simplex method on a decomposed and restricted problem. An auxiliary problem generates new va-riables not present initially. In this thesis, we focus our interest on the cases where the auxiliary problcm is a constrained shortest path problem in a graph. Various improvcments have been proposed in thc literature, but they arc all limitcd to a particular problem. This thesis proposes to facilitate thc reuse of those improvcments in different problems. For this, we propose a generic formalism to model such problems and a description of thc scarch for solutions using goals. We then present new and different practical improvements applicable te varions problems. More precisely, the contributions are : an efficient algorithm for elcmentary shortcst path in the subproblem, a combination of expert heuristics and Constraint Programming in the subproblem, search strategies for the subproblem, a Constraint Programming global constraint for shortest path subproblem, cutting planes applied to the path-based master problem, heuristics and search strategies for the master problem. Those improvements are validated on three different real applications : ve-hicle routing, crew scheduling, and network design. For each of those applications, we produce several experimental results sho-wing how some combinations of the proposed contributions help to improve the ultimate solutions. Finally, a column and cut generation framework has been implemented that eases the development of such applications and that includes most of our pro-posal
Dongmo, Nguepi Guissel Lagnol. "Modèles mathématiques et numériques avancés pour la simulation du polymère dans les réservoirs pétroliers". Electronic Thesis or Diss., université Paris-Saclay, 2021. http://www.theses.fr/2021UPASG077.
Texto completo da fonteAn effective technique to increase production in an oil field is to inject a mixture of water and polymer. The viscosity of polymer reduces the mobility of water, which then pushes oil better, resulting in a higher extraction rate. The numerical simulation of such an enhanced oil recovery is therefore of paramount importance. However, despite decades of research, the modeling of polymer flows in porous media and its numerical resolution remains a difficult subject.On the one hand, the models traditionally used by reservoir engineers exhibit, in the best case, resonance-like singularities that make them weakly hyperbolic. Thisdefect gives rise to some complications but remains acceptable. In the worst case, when we wish to incorporate the effect of the inaccessible pore volume (IPV), themodels become non-hyperbolic, which exacerbates the numerical instabilities that are likely to appear.On the other hand, classical numerical schemes do not yield satisfactory results. Without IPV, the excessive diffusion around the contact wave causes the most relevant information to be lost. With IPV, the existence of complex eigenvalues generates exponential instabilities at the continuous level that must be addressed at the discrete level to avoid a premature stop of the code.The objective of this thesis is to remedy these difficulties. Regarding models, we analyze several IPV laws and show an equivalence between two of them. Furthermore, we propose reasonable sufficient conditions on the IPV law to enforce weak hyperbolicity of the flow system. Regarding schemes for the problem without IPV, we advocate a correction to improve the accuracy of contact discontinuities. For the problem with IPV, we design a relaxation method that guarantees the stability of the calculations for all IPV laws
Haddaoui, Khalil. "Méthodes numériques de haute précision et calcul scientifique pour le couplage de modèles hyperboliques". Thesis, Paris 6, 2016. http://www.theses.fr/2016PA066176/document.
Texto completo da fonteThe adaptive numerical simulation of multiscale flows is generally carried out by means of a hierarchy of different models according to the specific scale into play and the level of precision required. This kind of numerical modeling involves complex multiscale coupling problems. This thesis is thus devoted to the development, analysis and implementation of efficient methods for solving coupling problems involving hyperbolic models.In a first part, we develop and analyze a coupling algorithm for one-dimensional Euler systems. Each system of conservation laws is closed with a different pressure law and the coupling interface separating these models is assumed fix and thin. The transmission conditions linking the systems are modelled thanks to a measure source term concentrated at the coupling interface. The weight associated to this measure models the losses of conservation and its definition allows the application of several coupling strategies. Our method is based on Suliciu's relaxation approach. The exact resolution of the Riemann problem associated to the relaxed system allows us to design an extremely accurate scheme for the coupling model. This scheme preserves equilibrium solutions of the coupled problem and can be used for general pressure laws. Several numerical experiments assess the performances of our scheme. For instance, we show that it is possible to control the flow at the coupling interface when solving constrained optimization problems for the weights.In the second part of this manuscript we design two high order numerical schemes based on the discontinuous Galerkin method for the approximation of the initial-boundary value problem associated to Jin and Xin's model. Our first scheme involves only discretization errors whereas the second approximation involves both modeling and discretization errors. Indeed in the second approximation, we replace in some regions the resolution of the relaxation model by the resolution of its associated scalar equilibrium equation. Under the assumption of a possible characteristic coupling interface, we exactly solve the Riemann problem associated to the coupled model. This resolution allows us to design a high order numerical scheme which captures the possible boundary layers at the coupling interface. Finally, the implementation of our methods enables us to analyze quantitatively and qualitatively the modeling and discretization errors involved in the coupled scheme. These errors are functions of the mesh size, the degree of the polynomial approximation and the position of the coupling interface
Rodriguez, Garcia Javier. "Numerical study of dynamic relaxation methods and contribution to the modelling of inflatable lifejackets". Lorient, 2011. http://www.theses.fr/2011LORIS247.
Texto completo da fonteLa Relaxation Dynamique (RD) est une méthode numérique présentée en 1965 par A. S. Day dans l'ouvrage "The Engineer". Depuis 1983, avec les travaux présentés par P. Underwood, la méthode est de plus en plus utilisée. Depuis ces travaux fondateurs, la méthode de RD a trouvé de nombreuses applications, et plusieurs auteurs ont introduit différentes améliorations de la méthode en cherchant l'optimisation des calculs. Désormais, son utilisation s'est largement étendue aux domaines tels que la dynamique des structures (particulièrement la recherche de forme), la geomécanique ou la biomécanique. Dans le cadre de l'utilisation de la RD les chercheurs ont suivi deux chemins différents pour le choix d'une stratégie d'amortissement des oscillations: certains ont utilisé la RD combinée avec un amortissement visqueux et d'autres ont utilisé la RD combinée avec un amortissement cinétique. Néanmoins, très peu de comparaisons entre ces deux méthodes ont été exposées ayant par but d'aider à choisir l'une ou l'autre pour une application en particulier. Focalisés dans la recherche de forme de structures minces, le principal objectif de cette thèse est d'apporter une contribution au développement des méthodes de RD parallèlement à une revue des méthodes existantes en vue de les comparer. Un premier article scientifique est ainsi détaillé dans ce travail en comparant les différentes méthodes de RD avec les deux types d'amortissement, cinétique et visqueux, pour le cas particulier de la recherche de forme de structures gonflables. Puis un second papier est décrit, où une extension pour la méthode de RD avec amortissement cinétique est proposée. En tant qu'application des méthodes de RD étudiées, une contribution à la modélisation des gilets de sauvetage gonflables est exposée. Le but de cette partie de la thèse est d'introduire quelques contributions à la création d'un outil numérique permettant de tester le fonctionnement d'un gilet de sauvetage gonflable en situation en utilisant la méthode des Eléments Finis. Ce travail comprend la création d'un mannequin paramétré, une caractérisation grossière du textile technique impliqué, des améliorations concernant la simulation numérique du gonflage du gilet en utilisant la méthode de RD, et finalement une première approche à la dynamique de l'eau et la mécanique du contact qui seront présents dans la simulation globale
Benamar, Fayçal. "Transport terrestre multimodal de conteneurs maritimes : modèle de tournées simultanées des conteneurs et des véhicules". Châtenay-Malabry, Ecole centrale de Paris, 1995. http://www.theses.fr/1995ECAP0423.
Texto completo da fonteGdoura, Mohamed Khaled. "Problème de Stokes avec des conditions aux limites non-linéaires : analyse numérique et algorithmes de résolution". Caen, 2011. http://www.theses.fr/2011CAEN2021.
Texto completo da fonteThis work is a first step in the analysis of mathematical problems arising from numerical simulation of mold filling process by polymer melt which can slip on solid wall. We focus on Stokes problem with Tresca boundary conditions since numerical analysis of such problem is rare. In the first part of the manuscript we begin by setting the primal problem written as a variational inequality. The friction term is presented by a nondifferential function. Then, we propose a three field mixed formulation in which friction is dualized and div(u) = 0 is forced by the Lagrange multiplier p identified to the pressure. Existence and uniqueness of the solution of such formulation is guaranteed by continuous inf-sup condition that we prove. P1 bubble-P1 finite element for (u, p) and P1 for , defined on the Tresca boundary, are used to discretize the resulting problem. We prove that only two uncoupled discrete inf-sup conditions on the pressure p and the shear stress are sufficient to ensure the stability of the discrete problem. Optimal error estimates are derived. The second part is devoted to the estimation of the optimal value of relaxation parameters in the used algorithms, known as ALG2 & ALG3. Using equivalence between alternating-direction methods and augmented Lagrangian formulation, we write ALG2 & ALG3 as a dual evolution problem discretized by some classical splitting scheme involving multivalued maximal monotone operators. We prove the convergence of the algorithms, in continuous case, to the steady state solution of the dual evolution problem and we deduce the optimal value of relaxation parameters after stimating the rate convergence of the two algorithms. In the last part, we present two domain decomposition methods based on Uzawa algorithms to solve Stokes problem with slip boundary conditions. Numerical tests are carried out and a preconditioner is proposedfor the second approache
Corro, Caio. "Lagrangian Based Approaches for Lexicalized Tree Adjoining Grammar Parsing". Thesis, Sorbonne Paris Cité, 2018. http://www.theses.fr/2018USPCD051.
Texto completo da fonteIn linguistics and Natural Language Processing (NLP), syntax is the studyof the structure of sentences in a given language. Two approaches have mainlybeen considered to describe them: dependency structures and phrase-structures.A dependency links a pair of words together with its relation type whereas aphrase-structure describe a sentence by means of a hierarchy of word sets calledconstituents. In this thesis, we focus on phrase-structure parsing, that is thecomputation of the constituency structure of a given sentence. Context-FreeGrammars (CFGs) have been widely adopted by the NLP community due totheir simplicity and the low complexity of their parsing algorithms. However,CFGs are too limited in order to describe all phenomena observed in naturallanguage structures. Therefore, Lexicalized Tree Adjoining Grammars (LTAGs)have been widely studied as a plausible alternative, among others. They aremore expressive than CFGs but can also be parsed in polynomial time. Unfortunately,the best known algorithm has a O(n7) time complexity with n thelength of the input sentence. Thus, in practice most algorithms are based ongreedy methods which require fairly strong independence assumptions. Themain approach in the literature, called supertagging, lters the search space ina pre-processing step while ignoring long distance relationships, one of the mainmotivation for LTAGs.In the past years, combinatorial optimization techniques have been successfullyapplied to computationally challenging NLP tasks. We follow this line ofwork in the case of LTAG parsing. More precisely, in our setting, a given NLPproblem is reduced to a subgraph selection problem. As such, it has a genericform which may interest other research communities. Then we formulate thegeneric graph problem as an Integer Linear Program. Integer Linear Programinghas been widely studied and many optimization methods exist. We focus onLagrangian relaxation which previously received much attention from the NLPcommunity. Interestingly, the proposed algorithms can be parametrized to Et arange of different data without impacting eciency.Our erst contribution is a novel pipeline for LTAG parsing. Contrary tothe supertagging approach, we propose a pre-processing step which takes intoaccount relationships between words: well-nested dependency parsing with 2-bounded block degree. An algorithm with a O(n7) time complexity has beenproposed for this problem in the literature, which is similar to the standardLTAG parser complexity. In order to tackle the complexity challenge, we showthat it can be reduced to a subgraph selection problem which can be expressed23via a generic ILP. With our algorithm, the well-nested constraint can easily betoggled o and the block degree bound can be changed. Thus, as an example,it can be used for parsing problems related to other lexicalized grammars. Weexperiment on several problems showing the emciency and usefulness of ourmethod.Our second contribution is a novel approach for discontinuous constituentparsing. We introduce a variant of LTAG for this task. Parsing is then equivalentto the joint tagging and non-projective dependency parsing problem. Weshow that it can be reduced to the Generalized Maximum Spanning Arborescenceproblem which has been previously studied in the combinatorial optimizationliterature. A novel resolution algorithm based on Lagrangian relaxation isproposed. We experiment on two standard discontinuous constituent datasetsand obtain state-of-the-art results alongside competitive decoding speed
Marques, Guillaume. "Problèmes de tournées de véhicules sur deux niveaux pour la logistique urbaine : approches basées sur les méthodes exactes de l'optimisation mathématique". Thesis, Bordeaux, 2020. http://www.theses.fr/2020BORD0199.
Texto completo da fonteThe main focus of this thesis is to develop mathematical optimization based exact methods to solve vehicle routing problems in two-level distribution systems. In such a system, the first level involves trucks that ships goods from a distribution center to intermediate depots called satellites. The second level involves city freighters that are loaded with goods at satellites and deliver the customers. Each customer must be visited once. The two-echelon vehicle routing problem seeks to minimize the total transportation cost in such a distribution system.The first chapter gives an overview of the branch-and-cut-and-price framework that we use throughout the thesis.The second chapter tackles the Two-Echelon Capacitated Vehicle Routing Problem. We introduce a new route based formulation for the problem which does not use variables to determine product flows in satellites. We propose a new branching strategy which significantly decreases the size of the branch-and-bound tree. Most importantly, we suggest a new family of satellite supply inequalities, and we empirically show that it improves the quality of the dual bound at the root node of the branch-and-bound tree. Experiments reveal that our algorithm can solve all literature instances with up to 200 customers and 10 satellites. Thus, we double the size of instances which can be solved to optimality.The third chapter tackles the Two-Echelon Vehicle Routing Problem with Time Windows. We consider the variant with precedence constraints at the satellites: products should be delivered by an urban truck to a satellite before loading them to a city freighter. This is a relaxation of the synchronisation variant usually considered in the literature. We consider single-trip and multi-trip variants of this problem. In the first one, city freighters start from satellites and do a single trip. In the second one, city freighters start from a depot, load product at satellites, and do several trips. We introduce a route based formulation that involves an exponential number of constraints to ensure precedence relations. A minimum-cut based algorithm is proposed to separate these constraints. We also show how these constraints can be taken into account in the pricing problem of the column generation approach. Experiments show that our algorithm can solve to optimality instances with up to 100 customers. The algorithm outperforms significantly another recent approach proposed the literature for the single-trip variant of the problem. Moreover, the “precedence relaxation” is exact for single-trip instances.The fourth chapter considers vehicle routing problems with knapsack-type constraints in the master problem. For these problems, we introduce new route load knapsack cuts and separation routines for them. We use these cuts to solve to optimality three problems: the Capacitated Vehicle Routing Problem with Capacitated Multiple Depots, the standard Location-Routing Problem, and the Vehicle Routing Problem with Time Windows and Shifts. These problems arise when routes at first level of the two-level distribution system are fixed. Our experiments reveal computational advantage of our algorithms over ones from the literature
Hussein, Manal. "Comportement asymptotique des solutions d'équations de type Schrödinger non linéaires faiblement amorties". Thesis, Lille 1, 2009. http://www.theses.fr/2009LIL10083/document.
Texto completo da fonteOur aim in this thesis is to study the long time behavior of the solutions to somme dissipative equations. Our work is subdivided in four chapters. In the first chapter, we consider a simplified 1-D model of a weakly damped forced Davey-Stewartson equation, which is a partial differential equation of Schrödinger type with a non local nonlinearity and with forcing and damping terms. We prove the existence of a regular global attractor for the associated dynamical system. In the second chapter, we are interested in the Davey-Stewartson system in the elliptic-elliptic case. We prove the existence and the regularity of a global attractor for sufficient small initial datas. In the third chapter, we consider the non elliptic Schrödinger equation NES with a subcritical nonlinearity. We prove that the associated dynamical system has a global attractor for sufficient small initial datas. In the fourth chapter, we go back to the issue of the first and the second chapter, but with discrete time using the relaxation scheme. We prove the existence and the regularity of a global attractor for the infinite-dimensional discrete associated dynamical systems
Li, Jinfeng. "Localisation d'usines et de plates-formes dans la chaîne logistique". Troyes, 2010. http://www.theses.fr/2010TROY0008.
Texto completo da fonteThis thesis concerns the plant and transshipment point location problems in the supply chain with three layers: plants with limited production capacities, capacitated transshipment points (TPs), and customers with known demands. Firstly, we introduce a multi-capacity transshipment point location problem with multicommodity flow (LPFPP). This problem consists in locating TPs, determining the capacity for each open TP and organizing the shipments of products. A clustering-based scatter search is proposed to solve the LPFPP. Secondly, we consider a two-stage capacitated trans-shipment point location problem with handling costs (LPFCM). The latter are modeled in a realistic way by associating with each transshipment point a limited set of handling modules. We propose a hybrid method compromising a lagrangian relaxation, a weighted Dantzig-Wolfe decomposition and a path-relinking to solve the LPFCM. Lastly, we introduce a capacitated plant location problem with multicommodity flow (CLUMF) which determines where to locate plants and how to supply the clients. We propose a lagrangian-based method combined with a tabu search to solve the CLUMF. All of the proposed algorithms in this thesis are tested on new instances based on bench-marks from the literaturesa few seconds. 3) find optimal solutions for 50 bench-mark instances of TSCFLP for the first time. 4) reduce the optimality gap by 1. 2% on average for the CLRP
Wang, Guanglei. "Relaxations in mixed-integer quadratically constrained programming and robust programming". Thesis, Evry, Institut national des télécommunications, 2016. http://www.theses.fr/2016TELE0026/document.
Texto completo da fonteMany real life problems are characterized by making decisions with current information to achieve certain objectives. Mathematical programming has been developed as a successful tool to model and solve a wide range of such problems. However, many seemingly easy problems remain challenging. And some easy problems such as linear programs can be difficult in the face of uncertainty. Motivated by a telecommunication problem where assignment decisions have to be made such that the cloud virtual machines are assigned to servers in a minimum-cost way, we employ several mathematical programming tools to solve the problem efficiently and develop new tools for general theoretical problems. In brief, our work can be summarized as follows. We provide an exact formulation and several reformulations on the cloud virtual machine assignment problem. Then several valid inequalities are used to strengthen the exact formulation, thereby accelerating the solution procedure significantly. In addition, an effective Lagrangian decomposition is proposed. We show that, the bounds providedby the proposed Lagrangian decomposition is strong, both theoretically and numerically. Finally, a symmetry-induced model is proposed which may reduce a large number of bilinear terms in some special cases. Motivated by the virtual machine assignment problem, we also investigate a couple of general methods on the approximation of convex and concave envelopes for bilinear optimization over a hypercube. We establish several theoretical connections between different techniques and prove the equivalence of two seeming different relaxed formulations. An interesting research direction is also discussed. To address issues of uncertainty, a novel paradigm on general linear problems with uncertain parameters are proposed. This paradigm, termed as multipolar robust optimization, generalizes notions of static robustness, affinely adjustable robustness, fully adjustable robustness and fills the gaps in-between. As consequences of this new paradigms, several known results are implied. Further, we prove that the multipolar approach can generate a sequence of upper bounds and a sequence of lower bounds at the same time and both sequences converge to the robust value of fully adjustable robust counterpart under some mild assumptions
Fokou, Pelap Géraud. "Conception d'un famework pour la relaxation des requêtes SPARQL". Thesis, Chasseneuil-du-Poitou, Ecole nationale supérieure de mécanique et d'aérotechnique, 2016. http://www.theses.fr/2016ESMA0014/document.
Texto completo da fonteOntology (or Knowledge base) is a formal representation of knowledge as entities and facts related to these entities. In the past years, several ontologies have been developed in academic and industrial contexts.They are generally defined with RDF language and querying with SPARQL language. A partial knowledge of instances and schema of ontology may lead user to execute queries that result in empty answers, considered as unsatisfactory. Among cooperative querying techniques which have been developed to solve the problem of empty answers, query relaxation technique is the well-known and used. It aims at weakening the conditions expressed in the original query to return alternative answers to the user. Existing work on relaxation of SPARQL queries we suffer from many drawbacks : (1) they do not allow defining in precise way the relaxation to perform with the ability to control the relaxation process (2) they do not identify the causes of failure of the request expressed by the user and (3) they do not include interactive tools to better exploit the relaxation techniques proposed. To address these limitations, this thesis proposes an advanced framework forquery relaxation SPARQL. First, this framework includes a set of relaxation operators dedicated to SPARQLqueries, to incrementally relax specific parts of the user request while controlling the relevance of the alternative responses returned w.r.t. to the user needs expressed in his request. Our framework also provides both several algorithms that identify the causes of failure of the user query and queries that are successful with a maximum number of conditions initially expressed in the failing request. This information allows the user to better understand why his request fails and execute queries that return non-empty alternative results. Finally,our framework offers intelligent relaxation strategies that rely on the causes of query failure. Such strategies reduce the execution time of the relaxation process compared to the traditional approach, which executes relaxed requests, based on their similarity to the user request, until a number of satisfactory alternative results is obtained. All contributions proposed in this framework were implemented and validated by experiments and scenarios based on the tests bench LUBM. They show the interest of our contributions w.r.t. the state of theart