Lagrangian-informed mixed integer programming reformulations

La programmation linéaire en nombres entiers est une approche robuste qui permet de résoudre rapidement de grandes instances de problèmes d'optimisation discrète. Toutefois, les problèmes gagnent constamment en complexité et imposent parfois de fortes limites sur le temps de calcul. Il devient alors nécessaire de développer des méthodes spécialisées afin de résoudre approximativement ces problèmes, tout en calculant des bornes sur leurs valeurs optimales afin de prouver la qualité des solutions obtenues. Nous proposons d'explorer une approche de reformulation en nombres entiers guidée par la relaxation lagrangienne. Après l'identification d'une forte relaxation lagrangienne, un processus systématique permet d'obtenir une seconde formulation en nombres entiers. Cette reformulation, plus compacte que celle de Dantzig et Wolfe, comporte exactement les mêmes solutions entières que la formulation initiale, mais en améliore la borne linéaire: elle devient égale à la borne lagrangienne. L'approche de reformulation permet d'unifier et de généraliser des formulations et des méthodes de borne connues. De plus, elle offre une manière simple d'obtenir des reformulations de moins grandes tailles en contrepartie de bornes plus faibles. Ces reformulations demeurent de grandes tailles. C'est pourquoi nous décrivons aussi des méthodes spécialisées pour en résoudre les relaxations linéaires. Finalement, nous appliquons l'approche de reformulation à deux problèmes de localisation. Cela nous mène à de nouvelles formulations pour ces problèmes; certaines sont de très grandes tailles, mais nos méthodes de résolution spécialisées les rendent pratiques.

Distribution-Free Bounds for Serial Correlation Coefficients in Heteroskedastic Symmetric Time Series

We consider the problem of testing whether the observations X1, ..., Xn of a time series are independent with unspecified (possibly nonidentical) distributions symmetric about a common known median. Various bounds on the distributions of serial correlation coefficients are proposed: exponential bounds, Eaton-type bounds, Chebyshev bounds and Berry-Esséen-Zolotarev bounds. The bounds are exact in finite samples, distribution-free and easy to compute. The performance of the bounds is evaluated and compared with traditional serial dependence tests in a simulation experiment. The procedures proposed are applied to U.S. data on interest rates (commercial paper rate).

Extension of Wu-Peters bounds to Catmull-Clark and 4-8 subdivision

La méthode de subdivision Catmull-Clark ainsi que la méthode de subdivision Loop sont des normes industrielle de facto. D'autre part, la méthode de subdivision 4-8 est bien adaptée à la subdivision adaptative, parce que cette méthode augmente le nombre de faces ou de sommets par seulement un facteur de 2 à chaque raffinement. Cela promet d'être plus pratique pour atteindre un niveau donné de précision. Dans ce mémoire, nous présenterons une méthode permettant de paramétrer des surfaces de subdivision de la méthode Catmull-Clark et de la méthode 4-8. Par conséquent, de nombreux algorithmes mis au point pour des surfaces paramétriques pourrant être appliqués aux surfaces de subdivision Catmull-Clark et aux surfaces de subdivision 4-8. En particulier, nous pouvons calculer des bornes garanties et réalistes sur les patches, un peu comme les bornes correspondantes données par Wu-Peters pour la méthode de subdivision Loop.

«School choice with controlled choice constraints: hard bounds versus soft bounds»

Controlled choice over public schools attempts giving options to parents while maintaining diversity, often enforced by setting feasibility constraints with hard upper and lower bounds for each student type. We demonstrate that there might not exist assignments that satisfy standard fairness and non-wastefulness properties; whereas constrained non-wasteful assignments which are fair for same type students always exist. We introduce a "controlled" version of the deferred acceptance algorithm with an improvement stage (CDAAI) that finds a Pareto optimal assignment among such assignments. To achieve fair (across all types) and non-wasteful assignments, we propose the control constraints to be interpreted as soft bounds-flexible limits that regulate school priorities. In this setting, a modified version of the deferred acceptance algorithm (DAASB) finds an assignment that is Pareto optimal among fair assignments while eliciting true preferences. CDAAI and DAASB provide two alternative practical solutions depending on the interpretation of the control constraints. JEL C78, D61, D78, I20.

Exact Lagrangian cobordism and pseudo-isotopy

Dans cette thèse, on étudie les propriétés des sous-variétés lagrangiennes dans une variété symplectique en utilisant la relation de cobordisme lagrangien. Plus précisément, on s'intéresse à déterminer les conditions pour lesquelles les cobordismes lagrangiens élémentaires sont en fait triviaux. En utilisant des techniques de l'homologie de Floer et le théorème du s-cobordisme on démontre que, sous certaines hypothèses topologiques, un cobordisme lagrangien exact est une pseudo-isotopie lagrangienne. Ce resultat est une forme faible d'une conjecture due à Biran et Cornea qui stipule qu'un cobordisme lagrangien exact est hamiltonien isotope à une suspension lagrangianenne.