Séminaire Optimisation Mathématique Modèle Aléatoire et Statistique

On s'intéresse au problème d'optimiser une fonction objectif g(W x) + c^T x pour x entier, où chaque coordonnée de x est contrainte dans un intervalle. On suppose que la matrice W est à coefficient entiers de valeur absolue bornée par Delta, et qu'elle projette x sur un espace de petite dimension m << n. Ce problème est une généralisation du résultat de Hunkenschröder et al. dans lequel g est séparable convexe, et x est dans un 0-1 hypercube.

On présentera un algorithme en complexité n^m (m Delta)^O(m^2), sous la supposition que l'on sache résoudre efficacement le problème lorsque n = m. Cet algorithme utilise les travaux d'Eisenbrand et Weismantel sur la programmation linéaire entière avec peu de contraintes.

L'algorithme présenté peut être employé théoriquement dans plusieurs problèmes notamment la programmation mixte linéaire avec peu de contraintes, ou encore le problème du sac à dos où l'on doit acheter son sac.

Separable states are multipartite quantum states that can be written as a convex combination of product states. Product states are multipartite quantum states that can be written as a tensor product of states in each space. Quantum state separable problem is an NP-hard problem but fundamental for quantum information theory. We propose two relaxation techniques for this problem. In the view of commutative optimization, we treat the states as matrices of multilinear complex polynomials. Our relaxation technique is found similar to that for complex bilinear polynomials arising in the Alternating Current Optimal Power Flow problem. In the view of non-commutative optimization, we treat the states as tensor products of bounded Positive Semi-definite variables. We propose a generalized McCormick relaxations using linear matrix inequalities. These two relaxations will be the key component to drive an exact branch-and-cut algorithm.

Hub Labeling (HL) is a state-of-the-art method for answering shortest-distance queries between node pairs in weighted graphs. It provides very fast query times but also requires considerable additional space to store the label information. Recently, a generalization of HL, called Landmark Hub Labeling (LHL), has been proposed, that conceptionally allows a storage of fewer label information without compromising the optimality of the query result. However, query answering with LHL was shown to be slower than with HL, both in theory and practice. Furthermore, it was not clear whether there are graphs with a substantial space reduction when using LHL instead of HL. 

In this talk, we describe a new way of storing label information of an LHL such that query times are significantly reduced and then asymptotically match those of HL. We establish novel bounds between different labeling variants and provide a comparative experimental study between approximation algorithms for HL and LHL. We demonstrate that label sizes in an LHL are consistently smaller than those of HL across diverse benchmark graphs, including road networks.

Cette recherche est menée pour examiner une approche d'optimisation distributionnellement robuste appliquée au problème de dimensionnement de lots avec des retards de production et une incertitude de rendement sous des ensembles d'ambiguïté par événement. Les ensembles d'ambiguïté basés sur les moments, Wasserstein et le clustering K-Means sont utilisés pour représenter la distribution des rendements. Des stratégies de décision statiques et statiques-dynamiques sont également considérées pour le calcul d'une solution. Dans cette présentation, la performance de différents ensembles d'ambiguïté sera présentée afin de déterminer un plan de production qui soit satisfaisant et robuste face aux changements de l'environnement. Il sera montré, à travers une expérience numérique, que le modèle reste traitable pour tous les ensembles d'ambiguïté considérés et que les plans de production obtenus demeurent efficaces pour différentes stratégies et contextes décisionnels.

In this presentation, a response matrix (here, species abundances) is assumed to depend on explanatory variables (here, environmental variables) supposed many and redundant, thus demanding dimension reduction. The Supervised Component-based Generalized Linear Regression (SCGLR), a Partial Least Squares-type method, is designed to extract from the explanatory variables several components jointly supervised by the set of responses. However, this methodology still has some limitations we aim to overcome in this work. The first limitation comes from the assumption that all the responses are predicted by the same explanatory space. As a second limitation, the previous works involving SCGLR assume the responses independent conditional on the explanatory variables. Again, this is not very likely in practice, especially in situations like those in ecology, where a non-negligible part of the explanatory variables could not be measured. To overcome the first limitation, we assume that the responses are partitioned into several unknown groups. We suppose that the responses in each group are predictable from an appropriate number of specific orthogonal supervised components of the explanatory variables. The second work relaxes the conditional independence assumption. A set of few latent factors models the residual covariance matrix of the responses conditional on the components. The approaches presented in this work are tested on simulation schemes, and then applied on ecology datasets.