Research interests

My research interests are

I have been applying these techniques to I am also interested in


Papers

Quadratic stabilization of Benders decomposition
Sofia Zaourar, Jérôme Malick
(under revision, 2014)
[HAL]
Abstract The foundational Benders decomposition, or variable decomposition, is known to have the inherent instability of cutting plane-based methods. Several techniques have been proposed to improve this method, which has become the state of the art for important problems in operations research. This paper presents a complementary improvement featuring quadratic stabilization of the Benders cutting-plane model. Inspired by the level-bundle methods of nonsmooth optimization, this algorithmic improvement is designed to reduce the number of iterations of the method. We illustrate the interest of the stabilization on two classical problems: network design problems and hub location problems. We also prove that the stabilized Benders method has the same theoretical convergence properties as the usual Benders method.

Nonsmooth optimization using uncontrolled inexact information
Jérôme Malick, Welington de Oliveira and Sofia Zaourar
(under revision, 2013)
Abstract We consider convex nonsmooth optimization problems whose objective function is known through a (fine) oracle together with some additional (cheap but poor) information – formalized as a second coarse oracle with uncontrolled inexactness. It is the case when the objective function is itself the output of an optimization solver, using a branch-and-bound procedure, or decomposing the problem into parallel subproblems. Minimizing such objective function can be done by any bundle algorithm using only the (fine) oracle. In this paper, we propose a general scheme to incorporate the available coarse information into bundle-type methods in view of generating better iterates and then accelerating the algorithms. We study two practical versions of the scheme: a (simple) inexact Kelley method, and a (sophisticated) level bundle method. We prove that these methods are convergent, and we present numerical illustrations showing they speed up resolution.

Variable size vector bin packing heuristics - Application to the machine reassignment problem
Michaël Gabay and Sofia Zaourar
Accepted for publication in Annals of Operations Research, 2014
[HAL]
Abstract In this paper, we introduce a generalization of the vector bin packing problem, where the bins have variable sizes. This generalization can be used to model virtual machine placement problems and in particular to build feasible solutions for the machine reassignment problem. We propose several families of greedy heuristics for this problem and show that they are flexible and can be adapted to handle additional constraints. We present structural properties of the machine reassignment problem, that allow us to decompose it into smaller subproblems and adapt our heuristics to them. We evaluate our heuristics on academic benchmarks of the vector bin packing problem, a randomly generated vector bin packing with heterogeneous bins benchmark as well as Google's realistic instances of the machine reassignment problem.

Prices stabilization for inexact unit-commitment problems
Sofia Zaourar and Jérôme Malick
Mathematical Methods of Operations Research, 78(3):341-359, 2013.
[HAL]
Abstract A widespread and successful approach to tackle unit-commitment problems is constraint decomposition: by dualizing the linking constraints, the large-scale nonconvex problem decomposes into smaller independent subproblems. The dual problem consists then in finding the best Lagrangian multiplier (the optimal “price”); it is solved by a convex nonsmooth optimization method. Realistic modeling of technical production constraints makes the subproblems themselves difficult to solve exactly. Nonsmooth optimization algorithms can cope with inexact solutions of the subproblems. In this case however, we observe that the computed dual solutions show a noisy and unstable behaviour, that could prevent their use as price indicators. In this paper, we present a simple and easy-to-implement way to stabilize dual optimal solutions, by penalizing the noisy behaviour of the prices in the dual objective. After studying the impact of a general stabilization term on the model and the resolution scheme, we focus on the penalization by discrete total variation, showing the consistency of the approach. We illustrate our stabilization on a synthetic example, and real-life problems from EDF (the French Electricity Board).

Invited talks

Optimisation convexe non-différentiable et méthodes de décomposition en recherche opérationnelle
Laboratoire G-SCOP, Grenoble, France, March 2015.
Accelerating Benders decomposition by level stabilization
ROADEF 2014, Bordeaux, France, February 2014.
Exploiting uncontrolled information in nonsmooth optimization methods
PGMO conference, Paris, October 2013.
COCONA Seminar Series, Kelowna, Canada, May 2013.
SCAIM Seminar, Vancouver, Canada, April 2013.
Prices stabilization for inexact unit-commitment problems
ISMP2012, 21st International Symposium on Mathematical Programming
Berlin, Germany, August 2012.

Contributed talks

Méthodes de faisceaux avec oracle inexact et incontrôlé
Journées du GdR MOA 2013, Paris, June 2013.
Stabilisation d'une méthode d'optimisation par décomposition
Journées du GdR MOA 2012, Saint-François, Guadeloupe, June 2012.
Total variation stabilization of inexact prices for unit-commitment problems
Workshop advanced optimisation methods and their applications to unit commitment in energy management, Clamart, France, November 2011.

Master thesis

Stabilizing price decomposition [report]

Research internship

Solving exactly graph bipartition problem [wiki page]