3 présentations

• 
  10h30 - 10h55

  Design and stabilization of an enhanced Benders decompositon algorithm to solve two-stage linear stochastic programs

  • Xavier Blanchot,
  • François Clautiaux, Centre Inria de l'université de Bordeaux
  • Boris Detienne, Centre Inria de l'université de Bordeaux
  • Aurélien Froger, prés., Centre Inria de l'université de Bordeaux
  • Manuel Ruiz, RTE

  We introduce a new exact algorithm to solve two-stage stochastic linear programs formulated with a large discrete set of scenarios. This algorithm solves the multicut Benders reformulation of such problems in a different way from the standard approach. It partitions subproblems into batches and checks whether the current first-stage candidate solution cannot be proven optimal after solving each batch of subproblems. The algorithm aggregates cuts by batches before adding them to the master problem. To avoid strong oscillations of the first-stage variables, we introduce a general framework to stabilize our algorithm and show its finite convergence and exact behavior. Extensive computational study on large-scale instances of the stochastic optimization literature shows its efficiency in comparison with alternative generic algorithms from the literature.

• 
  10h55 - 11h20

  A Stochastic Levenberg-Marquardt Method for Nonsmooth Regularized Inverse Problems

  • Valentin Dijon, prés., GERAD - Polytechnique Montréal
  • Dominique Orban, GERAD - Polytechnique Montréal
  • Youssef Diouane, ISAE-SUPAERO, Université de Toulouse, Toulouse, 31055 Cedex 4, France

  We consider a variant of the well-known Levenberg-Marquardt method to minimize the sum of a nonlinear least-squares term and a nonsmooth regularizer.

  With large-scale problems in mind, our algorithm is stochastic in the sense that it allows inexact stochastic evaluations of both the least-squares residual and its Jacobian.

  The stochastic process defined by the proposed method is shown to generate a sequence of iterates that converge to a first-order stationary point with respect to a stationarity metric.

  Worst case complexity results are also derived.

  We describe a Julia implementation of our method and report numerical experience on large problems arising from data science and computer vision.

• 
  11h20 - 11h45

  The Sample Average Approximation Method for Solving Two-Stage Stochastic Programs with Endogenous Uncertainty

  • Maria Carolina Bazotte Corgozinho, prés., Polytechnique Montreal
  • Margarida Carvalho, Université de Montréal
  • Thibaut Vidal, CIRRELT & SCALE-AI Chair in Data-Driven Supply Chains, Polytechnique Montréal

  Real-world decision-making problems involve Type 1 decision-dependent uncertainty, where the probability distribution of the stochastic process depends on the model decisions. However, few studies focus on two-stage stochastic programs with this type of endogenous uncertainty, and those that do lack general methodologies. We thus propose herein a general method for solving a class of these programs based on the transformation of random variables, a technique widely employed in probability and statistics. The proposed method is tailored to large-scale problems with discrete or continuous endogenous random variables. The random variable transformation allows the use of the sample average approximation (SAA) method, which provides optimality convergence guarantees under certain conditions. We show that, for some classical distributions, the proposed method reduces to solving mixed-integer linear or convex programs. Finally, we validate this method by applying it to a network design and facility-protection problem, considering distinct decision-dependent distributions for the random variables. Whereas most distributions result in a nonlinear nonconvex deterministic equivalent program, the proposed method solves mixed-integer linear programs in all cases. In addition, it produces attractive performance estimators for the SAA method in a reasonable computational time and outperforms the case in which the endogenous distribution defines a mixed-integer deterministic equivalent.