Journée Axe PMNL

Onglets principaux

Organisateur:

Intitulé: 
Journée Programmation mathématique non linéaire (axe PMNL du GDR RO)
Date: 
Lundi, 9 Décembre, 2024
Formulaire d'inscription (voir onglet Register ci-dessus): 

Informations pratiques

Programme

09:30-10:00 : Accueil des participants
10:00-10:45 : Quantum computing for optimization: a tour d'horizon in variational algorithms with some look at quadratic assignment problems and beyond, Andrea Simonetto (ENSTA, France)
10:45-11:30 : Learning for Nonlinear Optimization Problems, Bissan Ghaddar (Ivey Business School, Canada)
11:30-11:45 : Pause
11:45-12:30 : On partial convexifications of quadratically constrained sets containing indicator variables, Renaud Chicoisne (U. Clermont-Ferrand, France)
12:30-14:00 : Pause déjeuner
14:00-14:30 : Impact of Hydropower Production Function Approximations on Generator Maintenance Scheduling, Maïssa Daadaa (École Polytechnique, France)
14:30-14:45 : Pause
14:45-16:00 : Tutorial: modelling and solving nonlinear problems, Florian Fontan (Artelys, France)

Exposés invités

  • Renaud Chicoisne (U. Clermont-Ferrand, France)

Title: On partial convexifications of quadratically constrained sets containing indicator variables

Abstract: We study a set S defined by the epigraph of a strictly convex quadratic function with indicators on the continuous variables. 
More formally, a (2n+1) dimensional tuple (x,z,t) belongs to S if 
t >= x’Qx with Q positive definite (PD)
each of the n binary components of z indicates if the corresponding component of x is nonzero (on-off constraints)
For any subset of {1,…,n} of cardinality q, we derivate a closed form expression for the convex hull of S when keeping only q of the on-off constraints. We show that it reduces to extract a certain Schur complement from the PD matrix Q, and then convexify a lower dimensional set S’.
We show that this smaller convex hull can be rewritten in an extended space with a single SDP constraint of size (q+1)x(q+1).

When q=n, we recover a recent result of Wei et al. , Math. Prog. 204(1), 703-737 (2024). In their work, they also show that the optimization over S reduces to a *compact* mixed integer *linear* optimization problem: We show that our approach can generate strong cuts for that linear reformulation.

  • Maïssa Daadaa (École Polytechnique, France)

Title: Impact of Hydropower Production Function Approximations on Generator
Maintenance Scheduling.

Abstract: The generator maintenance scheduling problem in hydropower plants is a critical optimization challenge due to the nonlinear and nonconvex nature of the production function. To address this complexity and facilitate practical solutions, various approximation methods can be employed to represent the production function more effectively. In this study, three approximation are used: Convex hull approximation with hyperplanes, Polynomial approximation and Piecewise convex hull approximation. These methods are compared to assess their impact on maintenance scheduling. The analysis, based on data from five power plants across two seasons, provides insights into how the choice of approximation
influences maintenance decisions.

  • Florian Fontan (Artelys, France)

Title: Tutorial: modelling and solving nonlinear problems.

Abstract: The goal of this session is to get familiar with the tools used to model and solve nonlinear problems. We will see a couple of problems modeled with nonlinear programs, implemented in Python with the Pyomo modeler, and solved with the nonlinear programming solver Artelys Knitro.
Participants are expected to bring their computer with an up-to-date web browser. No installation will be required.

  • Bissan Ghaddar (Ivey Business School, Canada): 

    Title: Learning for Nonlinear Optimization Problems

    Abstract: The use of machine learning techniques to improve the performance of branch-and-bound optimization algorithms is a very active area in the context of mixed integer linear problems, but little has been done for non-linear optimization. To bridge this gap, we develop a learning framework for spatial branching and show its efficacy in the context of the Reformulation-Linearization Technique for polynomial optimization problems. The proposed learning is performed offline, based on instance-specific features and with no computational overhead when solving new instances. Novel graph-based features are introduced, which turn out to play an important role in the learning. Experiments on different benchmark instances from MINLPLib and QPLIB show that the learning-based branching selection and learning-based constraint generation significantly outperform the standard approaches.

  • Andrea Simonetto (ENSTA, France)

Title: Quantum computing for optimization: a tour d'horizon in variational algorithms with some look at quadratic assignment problems and beyond 

Abstract: Quantum computing is a new computing paradigm that has been advocated to be transformative for hard combinatorial optimization. The real picture is however more nuanced, having some quantum-based algorithms offering new heuristics to well-established problems. In this talk, I will give you a tour d'horizon in variational algorithms on quantum computers for combinatorial problems. I will point out challenges, opportunities, and the hope we have in make quantum optimization useful. In particular, I will present some initial results in quadratic assignment problems and permutation-based problems in general. ​