Seminars_2023_sept_dec

The presentation is about the following submitted paper:

François Clautiaux, Siham Essodaigui, Alain Nguyen, Ruslan Sadykov, Nawel Younes. (2023). Models and algorithms for configuring and testing prototype cars. (hal-04185248)

Contrary to classic classification and regression trees, built in a greedy heuristic manner, designing the tree model through an optimization problem allows us to easily include desirable properties in Machine Learning in addition to prediction accuracy. In this talk, we present a Non-Linear Optimization approach that is scalable with respect to the size of the training sample, and illustrate this flexibility to model several important issues in Explainable and Fair Machine Learning. These include sparsity, as a proxy for interpretability, by reducing the amount of information necessary to predict well; fairness, by aiming to avoid predictions that discriminate against sensitive features such as gender or race; the cost-sensitivity for groups of individuals in which prediction errors are more critical, such as patients of a disease, by ensuring an acceptable accuracy performance for them; local explainability, where the goal is to identify the predictor variables that have the largest impact on the individual predictions; as well as data complexity in the form of observations of functional nature. The performance of our approach is illustrated on real and synthetic data sets.

In this internal workshop, we review the recent literature on Lagrangian variable fixing techniques.

Finite adaptability is a resolution framework for two-stage robust optimization problems, introduced in 2010 by Bertsimas and Caramanis. We apply this resolution scheme for a glass industry production problem. The latter deals with coated glass production, in which thin layers of materials are deposited on the glass sheets, using a magnetron, to give it visual and thermal properties. The exact production plan is uncertain and the magnetron maintenance decisions have to be taken before the realization of the uncertainty.

A total matching of a graph G = (V,E) is a subset of G such that its elements, i.e. vertices and edges, are pairwise not adjacent. In this context, the Total Matching Problem calls for a total matching of maximum size. This problem generalizes both the Stable Set Problem, where we look for a stable set of maximum size and the Matching Problem, where instead we look for a matching of maximum size. In this talk, we present a polyhedral approach to the Total Matching Problem, and hence, we introduce the corresponding polytope, namely the Total Matching Polytope. To this end, we will present several families of nontrivial valid inequalities that are facet-defining for the Total Matching Polytope. In addition, we provide a first linear complete description for trees and complete bipartite graphs. For the latter family, the complete characterization is obtained by projecting a higher-dimension polytope onto the original space. This leads to also an extended formulation of compact size for the Total Matching Polytope of complete bipartite graphs.

We propose highly efficient heuristic and exact algorithms to solve the Electric Autonomous Dial-A-Ride Problem (E-ADARP), which consists in designing a set of minimum-cost routes that accommodates all customer requests for a fleet of Electric Autonomous Vehicles (EAVs). The E-ADARP has two important features: (i) the employment of EAVs and a partial recharging policy; (ii) the weighted-sum objective function that minimizes the total travel time and the total excess user ride time. We first propose a Deterministic Annealing (DA) algorithm to solve the E-ADARP. Partial recharging (i) is handled by an exact route evaluation scheme of linear time complexity. To tackle (ii), we propose a new method that allows effective computations of minimum excess user ride time by introducing a fragment-based representation of paths. To validate the performance of the DA algorithm, we compare our algorithm results to the best-reported Branch-and-Cut (B&C) algorithm results on existing instances. Our DA algorithm provides 25 new best solutions and 45 equal solutions for 84 existing instances. To test the algorithm’s performance on larger-sized instances, we establish new instances with up to 8 vehicles and 96 requests, and we provide 19 new solutions for these instances. Then, we present a highly efficient CG algorithm, which is integrated into the Branch-and-price (B&P) scheme to solve the E-ADARP exactly. Our CG algorithm relies on an effective labeling algorithm to generate columns with negative reduced costs. In the extension of labels, the key challenge is determining all excess-user-ride-time optimal schedules to ensure finding the minimum-negative-reduced-cost route. To handle this issue, we apply the fragment-based representation and propose a novel approach to abstract fragments to arcs while ensuring excess-user-ride-time optimality. We then construct a new graph that preserves all feasible routes of the original graph by enumerating all feasible fragments, abstracting them to arcs, and connecting them with each other, depots, and recharging stations in a feasible way. On the new graph, we apply strong dominance rules and constant-time feasibility checks to compute the shortest paths efficiently. In the computational experiments, we solve 71 out of 84 instances optimally, improve 30 previously reported lower bounds, and generate 41 new best solutions on previously solved and unsolved instances.

Problems involving the L0-norm have long been considered too difficult to solve, despite their practical interest. Recently, researchers from the discrete optimization community have shifted their attention towards this class of problems. Using tools traditionally employed in their field, they have unlocked the possibility to handle L0-norm problems in practice. In a first part, this talk will outline the applications of problems involving the L0-norm, their advantages and flaws, and will briefly review the history of the recent research works on this topic. Then, discrete optimization tools that can be used to address this type of problem will be presented. Specifically, we will focus on generic Mixed-Integer Program solvers and specialised Branch-and-Bound algorithms. Existing softwares for practitioners will also be discussed. In a last part, we will provide insights into the ongoing research directions regarding L0-norm problems and about the different researchers and laboratories involved.

The presentation is about a working paper on the maximum chordal sub-graph problem

Cutting planes are of crucial importance when solving nonconvex nonlinear programs to global optimality, for example using the spatial branch-and-bound algorithms. In this paper, we discuss the generation of cutting planes for signomial programming. Many global optimization algorithms lift signomial programs into an extended formulation such that these algorithms can construct relaxations of the signomial program by outer approximations of the lifted set encoding nonconvex signomial term sets, i.e., hypographs, or epigraphs of signomial terms. We show that any signomial term set can be transformed into the subset of the difference of two concave power functions, from which we derive two kinds of valid linear inequalities. Intersection cuts are constructed using signomial term-free sets which do not contain any point of the signomial term set in their interior. We show that these signomial term-free sets are maximal in the nonnegative orthant, and use them to derive intersection sets. We then convexify a concave power function in the reformulation of the signomial term set, resulting in a convex set containing the signomial term set. This convex outer approximation is constructed in an extended space, and we separate a class of valid linear inequalities by projection from this approximation. We implement the valid inequalities in a global optimization solver and test them on MINLPLib instances. Our results show that both types of valid inequalities provide comparable reductions in running time, number of search nodes, and duality gap.

The presentation is about the following submitted paper:

Xavier Blanchot, François Clautiaux, Aurélien Froger, Manuel Ruiz. (2023). Modeling and solving a stochastic generation and transmission expansion planning problem with a “Loss Of Load Expectation” reliability criterion. (hal-03957750v2)