1 |
Relaxations in mixed-integer quadratically constrained programming and robust programming / Relaxations en programmation mixte en nombres entiers avec contraintes quadratiques et en programmation robusteWang, Guanglei 28 November 2016 (has links)
De nombreux problèmes de la vie réelle sont exprimés sous la forme de décisions à prendre à l’aide de l’information accessible dans le but d’atteindre certains objectifs. La programmation numérique a prouvé être un outil efficace pour modéliser et résoudre une grande variété de problèmes de ce type. Cependant, de nombreux problèmes en apparence faciles sont encore durs à résoudre. Et même des problèmes faciles de programmation linéaire deviennent durs avec l’incertitude de l’information disponible. Motivés par un problème de télécommunication où l’on doit associer des machines virtuelles à des serveurs tout en minimisant les coûts, nous avons employé plusieurs outils de programmation mathématique dans le but de résoudre efficacement le problème, et développé de nouveaux outils pour des problèmes plus généraux. Dans l’ensemble, résumons les principaux résultats de cette thèse comme suit. Une formulation exacte et plusieurs reformulations pour le problème d’affectation de machines virtuelles dans le cloud sont données. Nous utilisons plusieurs inégalités valides pour renforcer la formulation exacte, accélérant ainsi l’algorithme de résolution de manière significative. Nous donnons en outre un résultat géométrique sur la qualité de la borne lagrangienne montrant qu’elle est généralement beaucoup plus forte que la borne de la relaxation continue. Une hiérarchie de relaxation est également proposée en considérant une séquence de couverture de l’ensemble de la demande. Ensuite, nous introduisons une nouvelle formulation induite par les symétries du problème. Cette formulation permet de réduire considérablement le nombre de termes bilinéaires dans le modèle, et comme prévu, semble plus efficace que les modèles précédents. Deux approches sont développées pour la construction d’enveloppes convexes et concaves pour l’optimisation bilinéaire sur un hypercube. Nous établissons plusieurs connexions théoriques entre différentes techniques et nous discutons d’autres extensions possibles. Nous montrons que deux variantes de formulations pour approcher l’enveloppe convexe des fonctions bilinéaires sont équivalentes. Nous introduisons un nouveau paradigme sur les problèmes linéaires généraux avec des paramètres incertains. Nous proposons une hiérarchie convergente de problèmes d’optimisation robuste – approche robuste multipolaire, qui généralise les notions de robustesse statique, de robustesse d’affinement ajustable, et de robustesse entièrement ajustable. En outre, nous montrons que l’approche multipolaire peut générer une séquence de bornes supérieures et une séquence de bornes inférieures en même temps et les deux séquences convergent vers la valeur robuste des FARC sous certaines hypothèses modérées / Many 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
|
2 |
MODELISATION MATHEMATIQUE ET SIMULATION NUMERIQUE DU DRAPE D'UN TEXTILEFare, Nadjombe 26 June 2002 (has links) (PDF)
L'objectif de ce travail est d'étudier la dé<br />formation d'un tissu posé sur un support bi- ou tri-dimensionnel et soumis à<br />son propre poids.<br />Dans la première partie, nous établissons les équations<br />d'équilibre de ce problème dans le cas général et<br />introduisons deux modèles mathématiques. Le premier est un<br />modèle membranaire non-linéaire, dont l'analyse mathématique<br />conduit au calcul de l'enveloppe quasi-convexe de la densité<br />d'énergie associée. Le deuxième modèle (modèle<br />membrane-flexion non-linéaire) est obtenu en ajoutant un terme<br />régularisant à une fonctionnelle énergie non coercive. Nous<br />prouvons l'existence d'au moins une solution de ce problème de<br />minimisation, en utilisant les techniques du Calcul des Variations. Enfin,<br />nous établissons l'existence de solutions pour le problème de<br />drapé tri-dimensionnel.<br />La seconde partie est consacrée à la résolution numérique des diffé%<br />rents modèles élaborés dans la première partie, au moyen d'une méthode ité%<br />rative de descente couplée avec une méthode multigrille, afin d'accélérer la<br />convergence de l'algorithme. Nous montrons que le problème discret admet au<br />moins une solution. Enfin, nous prouvons la convergence théorique d'une<br />sous-suite de solutions discrètes vers une solution du problème continu,<br />moyennant une hypothèse de densité.
|
Page generated in 0.0344 seconds