2023

Heure:	10:30 - 11:30
Lieu:	Salle C216, bâtiment C, Université de Villetaneuse
Résumé:	Theoretical and Computational comparison of Perspective Formulations for Piecewise Convex Problems
Description:	Claudia D’ambrosio Our study aims to generalize mathematical formulations for Piecewise Linear functions to Piecewise Convex functions, when they appears as part of mathematical optimization problems. In this seminar, we compare different formulations and show that their continuous relaxations are not equivalent when perspective reformulation is applied to strengthen the formulation of each single segment where the function is convex. Computational results on some classes of piecewise convex problems are presented

Heure:	10:30 - 11:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Identification des préférences structurées en choix social : quelques résultats algorithmiques et expérimentaux
Description:	Olivier Spanjaard Dans cet exposé, nous présenterons quelques résultats sur la reconnaissance de structures dans les préférences en décision collective. Plus précisément, étant donnée une collection de préférences de votants exprimées sous la forme de relations d'ordre complètes sur un même ensemble de candidats, on cherchera à déterminer si ses préférences respectent une structure commune sur les candidats, et si oui à identifier cette structure. Nous nous intéresserons au cas des préférences unimodales (single-peaked) sur un axe ou sur un graphe quelconque. Nous aborderons à la fois des aspects portant sur la justification de la pertinence des structures identifiées, des aspects algorithmiques et des aspects plus expérimentaux.

Heure:	10:30 - 11:30
Lieu:	Salle A303, bâtiment A, Université de Villetaneuse
Résumé:	Binary non-negative polynomials and convex certificates
Description:	Liding Xu We consider the problem of certifying the non-negativity of polynomials over the Boolean hypercube. We propose a new type of binary non-negativity certificate, which involves the signed support vector of the monomials occurring in the given polynomial. We employ known tools such as max flow and extensions of supermodular functions in order to construct our certificates. Especially, we examine the projected and extended LP formulations for the cone of our binary non-negativity certificates. Based on these tools, we show that a certain family of binary polynomials can be optimized in a fixed-parameter tractable way.

Heure:	10:30 - 11:30
Lieu:	Salle D214, bâtiment D, Université de Villetaneuse
Résumé:	Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems
Description:	Fabio Furini We study a family of discrete optimization problems asking for the maximization of the expected value of a concave, strictly increasing, and differentiable function composed with a set-union operator. The expected value is computed with respect to a set of coefficients taking values from a discrete set of scenarios. The function models the utility function of the decision maker, while the set-union operator models a covering relationship between two ground sets, a set of items and a set of metaitems. This problem generalizes the problem introduced by Ahmed S, Atamtürk A (Mathematical programming 128(1-2):149–169, 2011), and it can be modeled as a mixed integer nonlinear program involving binary decision variables associated with the items and metaitems. Its goal is to find a subset of metaitems that maximizes the total utility corresponding to the items it covers. It has applications to, among others, maximal covering location, and influence maximization problems. In the paper, we propose a double-hypograph decomposition that allows for projecting out the variables associated with the items by separately exploiting the structural properties of the utility function and of the set-union operator. Thanks to it, the utility function is linearized via an exact outer-approximation technique, whereas the set-union operator is linearized in two ways: either (i) via a reformulation based on submodular cuts, or (ii) via a Benders decomposition. We analyze from a theoretical perspective the strength of the inequalities of the resulting reformulations and embed them into two branch-and-cut algorithms. We also show how to extend our reformulations to the case where the utility function is not necessarily increasing. We then experimentally compare our algorithms inter se, to a standard reformulation based on submodular cuts, to a state-of-the-art global-optimization solver, and to the greedy algorithm for the maximization of a submodular function. The results reveal that, on our testbed, the method based on combining an outer approximation with Benders cuts significantly outperforms the other ones.