2025

Heure:	10:30 - 12:00
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	New formulations and algorithms for the optimal classification tree problem
Description:	Zacharie Ales Classification trees are models that provide highly interpretable classifiers but generally do not perform as well as neural networks. To obtain classifiers that are both interpretable and performant, we consider the problem of computing an optimal classification tree for a given data set. To address this problem, we first define new mathematical formulations in the form of mixed integer linear programs (MILP) and demonstrate that they are stronger and more efficient than state-of-the-art MILPs. To handle larger datasets, we then define iterative algorithms based on a data partition that is refined throughout the iterations.

Heure:	10:30 - 12:00
Lieu:	Salle A303, bâtiment A, Université de Villetaneuse
Résumé:	Scheduling Quantum Applications on Quantum Chips
Description:	Francesco Contu In this work we study the problem of scheduling quantum applications (i.e. quantum circuits) on shared quantum chips. Quantum computers are constrained by limited qubit connectivity and noisy operations, which makes the scheduling of quantum circuits on physical hardware a critical step for efficient execution. In this work, we model the scheduling problem as a tiling problem, under a set of assumptions that capture the main architectural restrictions of quantum chips. To address this problem, we propose an integer linear programming (ILP) formulation and present preliminary computational results.

Heure:	10:30 - 12:00
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	The neighborhood dominant polytope
Description:	Yue Zhang We propose a new polyhedral approach for combinatorial optimization problems. Rather than working on the convex hull of the feasible set, we focus on a polytope that excludes the uninteresting feasible solutions dominated in a local neighborhood. In this work, the idea is applied to the linear Knapsack problem and the quadratic MaxCut problem with a theoretical study that demonstrates dominance inequalities and facets. The outstanding effectiveness of the proposed inequalities is numerically shown on the MaxCut instances from the BiqBin library.