2017

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Reformulations de programmes quadratiques convexes en nombres entiers
Description:	Dominique Quadri La programmation quadratique en nombres entiers trouve de nombreuses applications dans le monde réel. Il semble important de développer des méthodes de résolution exactes permettant de résoudre en des temps CPU limités de tels problèmes. Or de nos jours les solveurs de programmation linéaire sont de plus en plus efficaces. C'est pourquoi cet exposé est axé sur des reformulations de programmes quadratiques en variables entières en programmes linéaires.

Heure:	12:30 - 13:00
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	A Column Generation approach for a Multi-Activity Tour Scheduling Problem
Description:	Stefania Pan

Heure:	13:00 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Simplicial Decomposition for Large-Scale Quadratic Convex Programming
Description:	Enrico Bettiol

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	On big data, optimization and learning
Description:	Prof. Andrea Lodi In this talk I review a couple of applications on Big Data that I personally like and I try to explain my point of view as a Mathematical Optimizer -- especially concerned with discrete (integer) decisions -- on the subject. I advocate a tight integration of Machine Learning and Mathematical Optimization (among others) to deal with the challenges of decision-making in Data Science. For such an integration I try to answer three questions: 1) what can optimization do for machine learning? 2) what can machine learning do for optimization? 3) which new applications can be solved by the combination of machine learning and optimization?

Heure:	11:30 - 12:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Valid quadratic inequalities for convex and some non-convex quadratic sets
Description:	Julio César Góez In recent years, the generalization of Balas disjunctive cuts for mixed integer linear optimization problems to mixed integer non-linear optimization problems has received significant attention. Among these studies, mixed integer second order cone optimization (MISOCO) is a special case. For MISOCO one has the disjuncti ve conic cuts approach. That generalization introduced the concept of disjunctive conic cuts (DCCs) and disjunctive cylindrical cuts (DCyCs). Specifically, it showed that under some mild assumptions the intersection of those DCCs and DCyCs with a closed convex set, given as the intersection of a second order cone and an affine set, is the convex hull of the intersection of the same set with a linear disjunction. The key element in that analysis is the use of pencils of quadrics to find close forms for deriving the DCCs and DCyCs. In this talk we present an overview of the DCCs main results and we use the same approach to show the existence of valid conic inequalities for hyperboloids and non-convex quadratic cones when the disjunction is defined by parallel hyperplanes. Joint work with Miguel F. Anjos.

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Deriving differential approximation results for k-CSPs from combinatorial designs
Description:	Sophie Toulouse Given two integers q, k ? 2, k-CSP?q is the unconstrained optimization problem in which variables have domain Z_q and the goal is to optimize a weighted sum of constraints, each acting on at most k of the variables. Standard inapproximability results for Max-k-CSP?q often involve balanced k-wise independent distributions over Z_q or rather equivalently, orthogonal arrays of strength k over Z_q. We here illustrate how combinatorial designs are a relevant tool in order to establish approximation results for k-CSP?q with respect to the differential approximation measure, which compares the distance between the approximate value and the worst solution value to the instance diameter. First, connecting the average differential ratio to orthogonal arrays, we deduce that this ratio is ?(1/n^(k/2)) when q = 2, ?(1/n^(k-1)) when q is a prime power and 1/q^k on (k+1)-partite instances. We also consider pairs of arrays that can be viewed as some constrained decomposition of balanced k-wise independent functions. We exhibit such pairs that allow when q > k to reduce k-CSP?q to k-CSP?k with an expansion 1/(q?k/2)^k on the approximation guarantee. This implies together with the result of [Yuri Nesterov, Semidefinite relaxation and nonconvex quadratic optimization, Optimization Methods and Software, 9 (1998), pp. 141–160] a lower approximability bound of 0.429/(q ? 1)^2 for 2-CSP?q. Similar designs also allow to establish that every Hamming ball with radius k provides a ?(1/n^k)-approximation of the instance diameter.