Mixed-integer nonlinear programs are typically solved using branch-and-bound algorithms. A key determinant of the success of such methods is their ability to construct tight and tractable relaxations. The predominant relaxation strategy used by most state-of-the-art solvers is the factorable programming technique. This technique recursively traverses the expression tree for each nonlinear function and relaxes each operator over a bounding box that covers the ranges for all the operands. While it is versatile, and allows finer control over the number of introduced variables, the factorable programming technique often leads to weak relaxations because it ignores operand structure while constructing the relaxation for the operator.<div>In this thesis, we introduce new relaxations, called composite relaxations, for composite functions by convexifying the outer-function over a polytope, which models an ordering structure of outer-approximators of inner functions. We devise a fast combinatorial algorithm to separate the hypograph of concave-extendable supermodular outer-functions over the polytope, although the separation problem is NP-Hard in general. As a consequence, we obtain large classes of inequalities that tighten prevalent factorable programming relaxations. The limiting composite relaxation obtained with infinitely many outer-approximators for each inner-function is shown to be related to the solution of an optimal transport problem. Moreover, composite relaxations can be seamlessly embedded into a discretization scheme to relax nonlinear programs with mixed-integer linear programs. Combined with linearization, composite relaxations provide a framework for deriving cutting planes used in relaxation hierarchies and more.<br></div>

We consider the survivable network design problem - the problem of designing, at minimum cost, a network with edge-connectivity requirements. As special cases, this problem encompasses the Steiner tree problem, the traveling salesman problem and the k-connected network design problem. We establish a property, referred to as the parsimonious property, of the linear programming (LP) relaxation of a classical formulation for the problem. The parsimonious property has numerous consequences. For example, we derive various structural properties of these LP relaxations, we present some algorithmic improvements and we perform tight worstcase analyses of two heuristics for the survivable network design problem.

This dissertation establishes mathematical foundations for the properties exhibited by generalizations of cliques, as well as algorithms to find such objects in a network. Cliques are a model of an ideal group with roots in social network analysis. They have since found applications as a part of grouping mechanisms in computer vision, coding theory, experimental design, genomics, economics, and telecommunications among other fields. Because only groups with ideal properties form a clique, they are often too restrictive for identifying groups in many real-world networks. This motivated the introduction of clique relaxations that preserve some of the various defining properties of cliques in relaxed form. There are six clique relaxations that are the focus of this dissertation: s-clique, s-club, s-plex, k-core, quasi-clique, and k-connected subgraphs. Since cliques have found applications in so many fields, research into these clique relaxations has the potential to steer the course of much future research. The focus of this dissertation is on bringing organization and rigorous methodology to the formation and application of clique relaxations. We provide the first taxonomy focused on how the various clique relaxations relate on key structural properties demonstrated by groups. We also give a framework for how clique relaxations can be formed. This equips researchers with the ability to choose the appropriate clique relaxation for an application based on its structural properties, or, if an appropriate clique relaxation does not exist, form a new one. In addition to identifying the structural properties of the various clique relaxations, we identify properties and prove propositions that are important computationally. These assist in creating algorithms to find a clique relaxation quickly as it is immersed in a network. We give the first ever analysis of the computational complexity of finding the maximum quasi-clique in a graph. Such analysis identifies for researchers the appropriate set of computational tools to solve the maximum quasiclique problem. We further create a polynomial time algorithm for identifying large 2-cliques within unit disk graphs, a special class of graphs often arising in communication networks. We prove the algorithm to have a guaranteed 1=2-approximation ratio and finish with computational results.

No description available.

Ce travail constitue une approche innovante mettant en complémentarité diverses techniques de caractérisation physicochimique, électrique et structurale. Menées sur un polymère époxyde, ces études ont pour principal objectif la compréhension des phénomènes et propriétés diélectriques associés aux charges d’espace, ainsi que le suivi de leur évolution dans le temps ou suite à l’application de contraintes extérieures. Les mesures de spectroscopie d’impédance et de courant de dépolarisation thermo-stimulé (CDTS), ont mis en évidence des processus de relaxations dipolaires et interfaciales. L’origine de ces phénomènes a pu être expliquée à partir des analyses physico-chimiques et structurales. Tout d’abord à l’aide des mesures de fluorescence X qui ont révélé la présence de deux types d’impuretés, pouvant créer des états énergétiques plus ou moins profonds dans la bande interdite. Ensuite, par des mesures en réflectométrie X qui ont mis en évidence plusieurs structures ordonnées au sein d’une matrice amorphe. Cette hétérogénéité structurale explique les mécanismes de piégeage et d’accumulation des charges d’espaces aux interfaces. De même, l’ordre local favorisant la mobilité des charges, ces résultats donnent une première réponse quant à la valeur relativement élevée de la conductivité électrique du polymère, telle qu’elle a pu être déterminée à partir des mesures des caractéristiques courant-tension. Des études de vieillissement accéléré ont également été menées. Les différents recuits appliqués ont contribué à la création de charges qui sont piégées dans des niveaux énergétiques de plus en plus profonds. Cela s’est traduit par une diminution de la quantité de charges qui relaxent par activation thermique ainsi que par une diminution de la conductivité électrique des échantillons. Ces changements de propriétés électriques ont été corrélés aux changements structuraux qui se sont produits au sein du polymère, et dont la principale manifestation est la disparition progressive des structures ordonnées. Cette disparition de l’ordre local a aussi été observée en l’absence de contraintes thermiques (vieillissement naturel), où il a été montré que le comportement superficiel et en volume des échantillons n’était pas identique. / This work constitutes an innovative approach in epoxy based polymer characterization, where complementary physico-chemical, electric and structural techniques are used. The main objective of these studies is to understand both dielectric phenomena and properties associated to the space charges, as well as to follow-up their evolution in time or after the application of external constraints.Impedance spectroscopy and thermo-stimulated depolarization current (TSDC), measurements have highlighted dipolar and interfacial relaxations processes. Origin of these phenomena has been explained from physico-chemical and structural analyses. First, X-ray fluorescence measurements revealed the presence of two types of impurities, which are able to create deep energetic levels in the forbidden energy band. Then, X ray reflectometry measurements highlighted several periodic structures within an amorphous matrix. This structural heterogeneity explains the mechanisms of trapping and accumulation of space charges at the interfaces and gives a first reply as for the relatively high value of the polymer electric conductivity, calculated from current-voltage measurements.Accelerated ageing studies have been also carried out. They have shown that annealing creates charges which are trapped in increasingly deep energetic levels. Consequently, both the quantity of released charges and annealed samples conductivities have decreased.These electric properties changes have been correlated with the structural changes occurring within the polymer, and whose principal manifestation is the progressive disappearance of the ordered structures. This disappearance of the local periodicity has also been observed in the absence of thermal constraints (natural ageing), where it was shown that samples surface’s behavior is different from the bulk.

<p>Efficient global dynamic optimization (GDO) using spatial branch-and-bound (SBB) requires the ability to construct tight bounds for the dynamic model. This thesis works toward efficient GDO by developing effective convex relaxation techniques for models with ordinary differential equations (ODEs). In particular, a novel algorithm, based upon a verified interval ODE method and the McCormick relaxation technique, is developed for constructing convex and concave relaxations of solutions of nonlinear parametric ODEs. In addition to better convergence properties, the relaxations so obtained are guaranteed to be no looser than their underlying interval bounds, and are typically tighter in practice. Moreover, they are rigorous in the sense of accounting for truncation errors. Nonetheless, the tightness of the relaxations is affected by the overestimation from the dependency problem of interval arithmetic that is not addressed systematically in the underlying interval ODE method. To handle this issue, the relaxation algorithm is extended to a Taylor model ODE method, which can provide generally tighter enclosures with better convergence properties than the interval ODE method. This way, an improved version of the algorithm is achieved where the relaxations are generally tighter than those computed with the interval ODE method, and offer better convergence. Moreover, they are guaranteed to be no looser than the interval bounds obtained from Taylor models, and are usually tighter in practice. However, the nonlinearity and (potentially) nonsmoothness of the relaxations impedes their fast and reliable solution. Therefore, the algorithm is finally modified by incorporating polyhedral relaxations in order to generate relatively tight and computationally cheap linear relaxations for the dynamic model. The resulting relaxation algorithm along with a SBB procedure is implemented in the MC++ software package. GDO utilizing the proposed relaxation algorithm is demonstrated to have significantly reduced computational expense, up to orders of magnitude, compared to existing GDO methods.</p> / Doctor of Philosophy (PhD)

La version classique du problème d'ordonnancement de projet à contraintes de ressources (RCPSP) consiste à trouver un ordonnancement, de durée minimale, des activités d'un projet entrant en compétition sur l'usage de ressources renouvelables, cumulatives et disponibles en quantité limité. <br />La réputation d'extrême difficulté du RCPSP a mené nombre de chercheurs à proposer de nouvelles méthodes de résolution exacte toujours plus performantes pour ce problème. Malgré cela, les instances de tailles réelles, qui se recontrent fréquemment, par exemple dans la gestion de production industrielle, sont encore loins d'être résolues optimalement. Il est donc intéressant, en combinant les acquis des travaux précédents, en particulier en programmation par contraintes (PPC) et en programmation linéaire (PL), de se pencher sur des méthodes exactes innovantes ou encore de développer des procédures d'évaluation par défaut, pour permettre une meilleure estimation de la performance des heuristiques sur le RCPSP. Ce travail de thèse entre dans ce cadre.<br /><br />Dans un premier temps, nous nous attachons au calcul de bornes inférieures pour le RCPSP par relaxation lagrangienne. D'une part, nous cherchons à accélerer le calcul de la borne de Brucker et Knust (obtenue par hybridation de PPC et de génération de colonnes) en résolvant le programme linéaire sous-jacent par relaxation lagrangienne (méthodes de sous-gradient et de génération de contraintes). D'autre part, nous appliquons le même principe de relaxation lagrangienne, sur la formulation linéaire initiale de Mingozzi et al. dont est extraite la relaxation préemptive utilisée par Brucker et Knust. Une partie du problème se réduit alors, comme indiqué par Möhring et al., au calcul d'une coupe minimale dans un graphe.<br /> <br />Nous étudions ensuite, un second type de bornes inférieures, obtenu par des méthodes de coupes basées sur les relaxations continues de deux formulations linéaires entières. Ces programmes linéaires sont au préalable resserés par des techniques éprouvées de propagation de contraintes, dont la règle globale du shaving. L'originalité de notre méthode repose essentiellement dans la génération des coupes qui sont, en grande partie, directement déduites des règles de propagation de contraintes.<br /><br />Enfin, nous proposons une méthode originale de résolution exacte pour le RCPSP, basée sur la procédure de Resolution Search de Chvàtal, une alternative aux méthodes de Branch-and-Bound classiques et qui se rapproche du Dynamic Backtracking en programmation par contraintes. Dans Resolution Search, l'espace de recherche ne se présente pas comme un arbre, puisqu'il s'agit, à chaque fois qu'un noeud terminal est rencontré, de rechercher par backtrakings successifs, les fixations minimales qui font de ce noeud un noeud terminal. L'ensemble des ces fixations est alors stocké de manière intelligente de façon à les exclure de l'espace de recherche. Resolution Search a été initialement développée pour la résolution de programmes linéaires en variables binaires, mais n'a semble-t'il jamais été employée dans le cadre de problèmes spécifiques.<br />Dans le but de prouver son efficacité, nous commencons par l'appliquer basiquement à deux formulations linéaires en variables binaires pour le RCPSP et la comparons à une version tout aussi basique de Branch-and-bound.<br /> Nous en poursuivons l'étude en utilisant des règles de branchement et d'évaluation ayant déjà prouvé leur efficacité dans des implémentations classiques de méthodes arborescentes pour le RCPSP, telles que celles de Brucker et al., Carlier et Latapie, Demeulemeester et Herroelen.

No description available.

No description available.

The fundamentally fluctuating nature of the strength of a wireless link poses a significant challenge when seeking to achieve reliable communication at high data rates. Common sense, supported by information theory, tells us that one can move closer towards achieving higher data rates if the transmitter is provided with a priori knowledge of the channel. Such channel knowledge is typically provided to the transmitter by a feedback channel that is present between the receiver and the transmitter. The quality of information provided to the transmitter is proportional to the bandwidth of this feedback channel. Thus, the design of feedback channels is a key aspect in enabling high data rates. In the past, these feedback channels have been designed locally, on a link-by-link basis. While such an approach can be globally optimal in some cases, in many other cases, this is not true. In this thesis, we identify various settings in wireless networks, some already a part of existing standards, others under discussion in future standards, where the design of feedback channels is a problem that requires global, network-wide optimization. In general, we propose the treatment of feedback bandwidth as a network-wide resource, as the next step en route to achieving Gigabit wireless. Not surprisingly, such a global optimization initiative naturally leads us to the important issue of computational efficiency. Computational efficiency is critical from the point-of-view of a network provider. A variety of optimization techniques are employed in this thesis to solve the large combinatorial problems that arise in the context of feedback allocation. These include dynamic programming, sub-modular function maximization, convex relaxations and compressed sensing. A naive algorithm to solve these large combinatorial problems would typically involve searching over a exponential number of possibilities to find the optimal feedback allocation. As a general theme, we identify and exploit special application-specific structure to solve these problems optimally with reduced complexity. Continuing this endeavour, we search for more intricate structure that enables us to propose approximate solutions with significantly-reduced complexity. The accompanying analysis of these algorithms studies the inherent trade-offs between accuracy, efficiency and the required structure of the problem. / text