2017

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.

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Derivative-Free Line search Methods for Solving Integer Programming Problems
Description:	Francesco Rinaldi In this talk, we describe some derivative-free methods for integer programming problems with both bound constraints on the variables and general nonlinear c onstraints. The approaches combine linesearches with a specific penalty approach for handling the nonlinear constraints. The use of both suitable generated search directions and specific stepsizes in the linesearch guarantee that all the points are generated in the integer lattice. We analyze the theoretical properties of the methods and show extensive numerical experiments on both bound constrained and nonlinearly constrained problems.

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Combinatorial optimization problems in networks
Description:	Nelson Maculan We present optimization models with a polynomial number of variables and constraints for combinatorial optimization problems in networks: optimum elementary cycles (whose traveling salesman problem), optimum elementary paths even in a graph with negative cycles, and optimum trees (whose Steiner tree problem) problems. Computational results for the Steiner tree problem are also presented.