O.R. Seminar - Alexandre Dupont-Bouillard

11/06/2026 - 15:00 - CORE C.035 - 

Alexandre Dupont-Bouillard

(Université de Rennes)

will give a presentation on

Polytopes associated with chordal graphs: induced path, induced trees and co-3-plexes

Abstract:

Given a graph G=(V,E), an induced path (resp. tree) is a set of vertices inducing path (resp. tree). We consider the convex hull of 0/1-vector in \mathbb{R}^V \times \mathbb{R}^E encoding induced path (resp. induced trees).

Our first main result is that, for chordal graphs, the incidence vectors of induced paths (respectively, induced trees) form a \emph{Hilbert basis}: every
integer vector in their conic hull can be expressed as a nonnegative integer combination of these incidence vectors. Hilbert bases are of interest in combinatorial optimization due to their close relationship with totally dual integral systems, which are known to yield integer polyhedra when their
right-hand side is integral.

Somewhat surprisingly, we do not exploit this connection directly. Instead, the Hilbert basis property allows us to derive linear descriptions of the
\emph{induced path polytope} and the \emph{induced tree polytope} of chordal graphs, defined as the convex hulls of the corresponding incidence vectors. The description we obtain for the induced tree polytope has polynomial size. For the induced path polytope, our initial system contains exponentially many inequalities; we therefore identify those defining facets and show that their
number is, in fact, polynomial.

These polyhedral characterizations imply that the problems of finding a maximum or minimum-weight induced path or induced tree are polynomially
solvable on chordal graphs.

Finally, we show how this result can be used to find maximum weight \emph{co-3-plexes}, that are sets of vertices inducing subgraphs of maximum degree 2. In fact, we exhibit a polynomial-time algorithm based on column generation solving the latter.

Dreze lecture by Raj Chetty

On June 12, 2026 at 2pm in Louvain-la-Neuve (Aula Magna) Raj Chetty will give a presentation on:
 

The Social Origins of Economic Opportunity:
Theory and Evidence

O.R. Seminar - Benedetto Manca

24/06/2026 - Euler building A.002

Benedetto Manca

 
(University of Cagliari)

will give a presentation on

Random Projections for Mathematical Programming

Abstract:

Random projections are random linear maps which approximately preserve geometrical quantities. The Johson-Lindenstrauss Lemma states that there exist random projections with a relatively small number of rows which preserve the pairwise Euclidean distances among a set of points.

In the past years several results on the application of random projections to Mathematical Programming instances are being obtained, showing that it is possible to obtain an approximate formulation with less decision variables and constraints and therefore easier to solve.

In this talk I will introduce the generic framework of random projections for Mathematical Programming formulations and I will present more in details some results in the case of Linear Programming, Quadratic Programming and the Minimum Sum of Squares problem.