Nesta tese, estudamos um arcabouço, introduzido por Frank, que denominamos de sistemas generalizados de núcleos. Provamos teoremas sobre empacotamentos de certos objetos combinatórios neste arcabouço, tanto para o caso inteiro quanto para o fracionário. Estes teoremas, em particular, implicam em uma melhora nos limitantes superiores de Schrijver, para o empacotamento de ramificações, e de Gabow e Manu, para o empacotamento de arborescências. Além disso, também provamos que o problema de minimização num poliedro relacionado pode ser resolvido em tempo polinomial, dado um oráculo de separação. / We study a framework, which we call a generalized kernel system, introduced by Frank. We prove some integral and fractional packing theorems on this framework which, in particular, imply an improvement on the best upper bounds currently known, one due to Schrijver, for packing branchings from a given root-sets, and another, due to Gabow and Manu, for packing spanning arborescences from a given root. We also establish the polynomial time complexity, modulo a separation oracle, of a related minimization problem involving a polyhedron derived from this framework.

Weber and Stidham (1987) used submodularity to establish transition monotonicity (a service completion at one station cannot reduce the service rate at another station) for Markovian queueing networks that meet certain regularity conditions and are controlled to minimize service and queueing costs. We give an extension of monotonicity to other directions in the state space, such as arrival transitions, and to arrival routing problems. The conditions used to establish monotonicity, which deal with the boundary of the state space, are easily verified for many queueing systems. We also show that, without service costs, transition-monotone controls can be described by simple control regions and switching functions, extending earlier results. The theory is applied to production/inventory systems with holding costs at each stage and finished goods backorder costs.

Weber and Stidham (1987) used submodularity to establish transition monotonicity (a service completion at one station cannot reduce the service rate at another station) for Markovian queueing networks that meet certain regularity conditions and are controlled to minimize service and queueing costs. We give an extension of monotonicity to other directions in the state space, such as arrival transitions, and to arrival routing problems. The conditions used to establish monotonicity, which deal with the boundary of the state space, are easily verified for many queueing systems. We also show that, without service costs, transition-monotone controls can be described by simple control regions and switching functions, extending earlier results. The theory is applied to production/inventory systems with holding costs at each stage and finished goods backorder costs.

We develop a class of models to represent the dynamics of a virus spreading in a cellphone network, employing a taxonomy that includes five key characteristics. Based on the resulting dynamics governing the spread, we present optimization models to rapidly detect the virus, subject to resource limitations. We consider two goals, maximizing the probability of detecting a virus by a time threshold and minimizing the expected time to detection, which can be applied to all spread models we consider. We establish a submodularity result for these two objective functions that ensures that a greedy heuristic yields a well-known constant-factor (63%) approximation. We relate the latter optimization problem, under a specific virus-spread mechanism from our class of models, to a classic facility-location model. Using data from a large carrier, we build several base cellphone contact networks of different scale. We then rescale these base networks using the so-called c-core decomposition that removes vertices of low degree in a recursive way. We further show that this down-sampling strategy preserves, in general, the topological properties of the base networks, based on testing several measures. For the objective that maximizes the probability that we detect a virus by a time threshold, we provide a sample-average optimization model that yields an asymptotically-optimal design for locating the detection devices, as the number of samples grows large. To choose a relevant time threshold, we perform a simulation for some spread models. We then test the performance of our proposed solution methods by solving the presented optimization models for some spread dynamics using some of the contact networks built after the c-core decomposition. The computational results show that the greedy algorithm is an efficient way to solve the corresponding sample-average approximation model, and the greedy solutions outperform some other simple solution approaches. / text

Nesta tese, estudamos um arcabouço, introduzido por Frank, que denominamos de sistemas generalizados de núcleos. Provamos teoremas sobre empacotamentos de certos objetos combinatórios neste arcabouço, tanto para o caso inteiro quanto para o fracionário. Estes teoremas, em particular, implicam em uma melhora nos limitantes superiores de Schrijver, para o empacotamento de ramificações, e de Gabow e Manu, para o empacotamento de arborescências. Além disso, também provamos que o problema de minimização num poliedro relacionado pode ser resolvido em tempo polinomial, dado um oráculo de separação. / We study a framework, which we call a generalized kernel system, introduced by Frank. We prove some integral and fractional packing theorems on this framework which, in particular, imply an improvement on the best upper bounds currently known, one due to Schrijver, for packing branchings from a given root-sets, and another, due to Gabow and Manu, for packing spanning arborescences from a given root. We also establish the polynomial time complexity, modulo a separation oracle, of a related minimization problem involving a polyhedron derived from this framework.

A cooperative multi-agent system is a collection of interacting agents deployed in a mission space where each agent is allowed to control its local state so that the fleet of agents collectively optimizes a common global objective. While optimization problems associated with multi-agent systems intend to determine the fixed set of globally optimal agent states, control problems aim to obtain the set of globally optimal agent controls. Associated non-convexities in these problems result in multiple local optima. This dissertation explores systematic techniques that can be deployed to either escape or avoid poor local optima while in search of provably better (still local) optima. First, for multi-agent optimization problems with iterative gradient-based solutions, a distributed approach to escape local optima is proposed based on the concept of boosting functions. These functions temporarily transform gradient components at a local optimum into a set of boosted non-zero gradient components in a systematic manner so that it is more effective compared to the methods where gradient components are randomly perturbed. A novel variable step size adjustment scheme is also proposed to establish the convergence of this distributed boosting process. Developed boosting concepts are successfully applied to the class of coverage problems. Second, as a means of avoiding convergence to poor local optima in multi-agent optimization, the use of greedy algorithms in generating effective initial conditions is explored. Such greedy methods are computationally cheap and can often exploit submodularity properties of the problem to provide performance bound guarantees to the obtained solutions. For the class of submodular maximization problems, two new performance bounds are proposed and their effectiveness is illustrated using the class of coverage problems. Third, a class of multi-agent control problems termed Persistent Monitoring on Networks (PMN) is considered where a team of agents is traversing a set of nodes (targets) interconnected according to a network topology aiming to minimize a measure of overall node state. For this class of problems, a gradient-based parametric control solution developed in a prior work relies heavily on the initial selection of its `parameters' which often leads to poor local optima. To overcome this initialization challenge, the PMN system's asymptotic behavior is analyzed, and an off-line greedy algorithm is proposed to systematically generate an effective set of initial parameters. Finally, for the same class of PMN problems, a computationally efficient distributed on-line Event-Driven Receding Horizon Control (RHC) solution is proposed as an alternative. This RHC solution is parameter-free as it automatically optimizes its planning horizon length and gradient-free as it uses explicitly derived solutions for each RHC problem invoked at each agent upon each event of interest. Hence, unlike the gradient-based parametric control solutions, the proposed RHC solution does not force the agents to converge to one particular behavior that is likely to be a poor local optimum. Instead, it keeps the agents actively searching for the optimum behavior. In each of these four parts of the thesis, an interactive simulation platform is developed (and made available online) to generate extensive numerical examples that highlight the respective contributions made compared to the state of the art.

This thesis is a detailed examination of the expressive power of valued constraints and related complexity questions. The valued constraint satisfaction problem (VCSP) is a generalisation of the constraint satisfaction problem which allows to describe a variety of combinatorial optimisation problems. Although most results are stated in this framework, they can be interpreted equivalently in the framework of, for instance, pseudo-Boolean polynomials, Gibbs energy minimisation, or Markov Random Fields. We take a result of Cohen, Cooper and Jeavons that characterises the expressive power of valued constraint in terms of certain algebraic properties, and extend this result by showing yet another connection between the expressive power of valued constraints and linear programming. We prove a decidability result for fractional clones. We consider various classes of valued constraints and the associated cost functions with respect to the question of which of these classes can be expressed using only cost functions of bounded arities. We identify the first known example of an infinite chain of classes of constraints with strictly increasing expressive power. We present a full classification of various classes of constraints with respect to this problem. We study submodular constraints and cost functions. Submodular functions play a key role in combinatorial optimisation and are often considered to be a discrete analogue of convex functions. It has previously been an open problem whether all Boolean submodular cost functions can be decomposed into a sum of binary submodular cost functions over a possibly larger set of variables. This problem has been considered within several different contexts in computer science, including computer vision, artificial intelligence, and pseudo-Boolean optimisation. Using a connection between the expressive power of valued constraints and certain algebraic properties of cost functions, we answer this question negatively. Our results have several corollaries. First, we characterise precisely which submodular polynomials of degree 4 can be expressed by quadratic submodular polynomials. Next, we identify a novel class of submodular functions of arbitrary arities that can be expressed by binary submodular functions, and therefore minimised efficiently using a so-called expressibility reduction to the (s,t)-Min-Cut problem. More importantly, our results imply limitations on this kind of reduction and establish for the first time that it cannot be used in general to minimise arbitrary submodular functions. Finally, we refute a conjecture of Promislow and Young on the structure of the extreme rays of the cone of Boolean submodular functions.

La conception de réseaux est un riche sous-domaine de l'optimisation combinatoire ayant de nombreuses applications pratiques. Du point de vue méthodologique, la plupart des problèmes de cette classe sont notoirement difficiles en raison de leur nature combinatoire et de l'interdépendance des décisions qu'ils impliquent. Ce mémoire aborde deux problèmes de conception de réseaux dont les structures respectives posent des défis bien distincts. Tout d'abord, nous examinons un problème déterministe dans lequel un client doit acquérir au prix minimum un certain nombre d'unités d'un produit auprès d'un ensemble de fournisseurs proposant différents coûts fixes et unitaires, et dont les stocks sont limités. Ensuite, nous étudions un problème probabiliste dans lequel une entreprise entrant sur un marché existant cherche, en ouvrant un certain nombre d'installations parmi un ensemble de sites disponibles, à maximiser sa part espérée d'un marché composé de clients maximisant une fonction d'utilité aléatoire. Ces deux problèmes, soit le problème de transport à coût fixe à un puits et le problème d'emplacement d'installations compétitif basé sur les choix, sont étroitement liés au problème du sac à dos et au problème de couverture maximale, respectivement. Nous introduisons de nouvelles reformulations prenant avantage de ces connexions avec des problèmes classiques d'optimisation combinatoire. Dans les deux cas, nous exploitons ces reformulations pour démontrer de nouvelles propriétés théoriques et développer des méthodes de résolution efficaces. Notre nouvel algorithme pour le problème de transport à coûts fixes à un puits domine les meilleurs algorithmes de la littérature, réduisant le temps de résolution des instances de grande taille jusqu'à quatre ordres de grandeur. Une autre contribution notable de ce mémoire est la démonstration que la fonction objectif du problème d'emplacement d'installations compétitif basé sur les choix est sous-modulaire sous n'importe quel modèle de maximisation d’utilité aléatoire. Notre méthode de résolution basée sur la simulation exploite cette propriété et améliore l'état de l'art pour plusieurs groupes d'instances. / Network design is a rich subfield of combinatorial optimization with wide-ranging real-life applications. From a methodological standpoint, most problems in this class are notoriously difficult due to their combinatorial nature and the interdependence of the decisions they involve. This thesis addresses two network design problems whose respective structures pose very distinct challenges. First, we consider a deterministic problem in which a customer must acquire at the minimum price a number of units of a product from a set of vendors offering different fixed and unit costs and whose supply is limited. Second, we study a probabilistic problem in which a firm entering an existing market seeks, by opening a number of facilities from a set of available locations, to maximize its expected share in a market composed of random utility-maximizing customers. These two problems, namely the single-sink fixed-charge-transportation problem and the choice-based competitive facility location problem, are closely related to the knapsack problem and the maximum covering problem, respectively. We introduce novel model reformulations that leverage these connections to classical combinatorial optimization problems. In both cases, we exploit these reformulations to prove new theoretical properties and to develop efficient solution methods. Our novel algorithm for the single-sink fixed-charge-transportation problem dominates the state-of-the-art methods from the literature, reducing the solving time of large instances by up to four orders of magnitude. Another notable contribution of this thesis is the demonstration that the objective function of the choice-based competitive facility location problem is submodular under any random utility maximization model. Our simulation-based method exploits this property and achieves state-of-the-art results for several groups of instances.