Detailed program

Abstract: Given two sets of points A and B in the d-dimensional space and integers a and b, we are interested in finding a axis-parallel hyper-rectangles associated with the set A and b axis-parallel hyper-rectangles associated with the set B such that (i) every point in A is contained in at least one hyper-rectangle associated with A, (ii) every point in B is contained in at least one hyper-rectangle associated with B, and (iii) the number of points from one set that are included into a hyper-rectangle corresponding to the other set is minimized. We refer to these points as "misclassified points". If the coordinate axes correspond to relevant parameters in the application domain, then axis-parallel hyper-rectangles provide easy-to-explain clusters. This setting corresponds to a supervised clustering problem, in which the points are already classified into two classes. We provide a branch and price approach for this problem that allows to find optimal solutions to larger instances than a compact formulation, and an iterative heuristic inspired by the classical k-means procedure. We explore the computational performance of this machinery, concluding that the heuristic allows to find good-quality solutions in acceptable running times.

Abstract: We study the problem of hyper-rectangular clustering, where data points are partitioned into a fixed number of clusters, each represented by an axis-aligned hyper-rectangle. A key modeling component in this setting is the definition of cluster size. Existing approaches typically rely on the $\ell_1$ norm of the side lengths (span), which yields tractable linear formulations but may fail to capture the geometric extent of clusters.

We introduce a new class of models based on Minkowski norms, focusing on the $\ell_2$ norm, where cluster size is defined as the Euclidean diameter of the corresponding hyper-rectangle. While this provides a more meaningful geometric measure, it leads to inherently nonlinear formulations. To address this challenge, we propose a linearization framework based on projections onto unit vectors. Our main contribution is a dynamic refinement scheme, the Lazy Vectors Method, which iteratively generates valid inequalities and converges to an exact representation of the Euclidean norm, enabling global optimization via mixed-integer linear programming.

The framework accommodates multiple objective functions, including sum, maximum, and lexicographic variants of cluster sizes. We further strengthen the formulations with valid inequalities and symmetry-breaking constraints, and develop heuristic procedures to obtain high-quality feasible solutions.

Computational experiments on synthetic instances show that the proposed approach is effective in practice, requiring only a small number of refinement iterations. The results demonstrate that Euclidean diameter-based clustering can be solved to optimality for instances of moderate size, providing a tractable and interpretable alternative to existing formulations.

Abstract: The design, management and analysis of complex networks demand a methodology that integrates large-scale data processing with mathematical optimization. Tasks such as clustering, facility location, routing, flow allocation, sensor placement, outlier detection, and user profiling share a common shortcoming in standard practice: data and design are handled separately and sequentially, forfeiting the substantial gains that true integration can provide.

This talk addresses one central challenge: integration of design, optimization and data science. The two driving forces of datafication and universalization of information impose a fundamental shift in network and location science: the sheer volume and complexity of modern data require advanced mathematical and machine learning tools at every phase of the analysis, from feature selection and intelligent segmentation to the optimization of problems that arise from the data themselves.

The goal is therefore twofold: (i) to incorporate data-science methodology into large-scale network analysis (handling “big data” with optimization tools), and (ii) reciprocally, to exploit network design and location models to improve machine learning tasks. We survey recent results from our research group illustrating how modern location-analysis techniques enhance regression, supervised and unsupervised classification, and community detection, eliminating the need for ad hoc, problem-specific reformulations.

Abstract: TBA

Abstract: Classification trees are among the most interpretable supervised classification models. Computing an optimal tree - one minimizing the number of misclassifications for a given depth - can be modelled as a mixed-integer linear program (MILP), which yields markedly smaller, and therefore more interpretable, trees than greedy heuristics such as CART. The drawback is scalability: the size of these formulations grows with the product of the number of data points and the size of the tree.

We first introduce new optimization models for the optimal classification tree problem. Expressing the number of misclassifications as a quadratic function of the routing and labelling variables allows several families of variables to be removed, and applying the Fortet and Glover linearizations yields new MILPs, in both the univariate and multivariate settings. Their continuous relaxations are shown to dominate that of the reference formulation of Bertsimas and Dunn (2017), and they are solved faster in practice.

We then address scalability through data-partitions. A data-partition replaces the dataset by a partition of the data points together with a representative and a label for each cluster, so that the MILP is solved on a much smaller instance. We introduce two algorithms which iteratively solve a MILP for a data-partition and refine it until all data points follow the same path as its representative in the computed tree. In the first one, the representatives are fixed which leads to a fast heuristic. In the second one, the representatives are decision variables chosen by the optimization process. We prove that this last model provides an optimal tree for the initial dataset. Numerical experiments illustrate the accuracy and the computational gains of both approaches.

Abstract: Agglomerative hierarchical clustering is typically performed via greedy heuristics that merge, at each step, the two closest clusters according to a linkage criterion (e.g., single- or complete-linkage). These local decisions, however, can lead to globally suboptimal dendrograms. This work introduces the first unified mixed-integer linear programming (MILP) formalization of agglomerative clustering, aimed at optimizing the entire sequence of merges rather than fixing it greedily. We propose two MILP formulations. The first one updates the distance matrix iteratively, embedding single- and complete-linkage rules, and an α-weighted combination of both, inspired by the Dunn Index, into the optimization. The second one, based on clique partitioning, explicitly models cluster membership at each level, enabling the computation of cophenetic distances and an alternative objective based on Goodman-Kruskal's Gamma. Together, these define the Optimal Dunn-Linkage (ODL) approach. Experiments on synthetic datasets show that both formulations produce higher-quality dendrograms than greedy algorithms, though exact optimality is limited to small instances. For larger datasets, we design a matheuristic combining greedy clustering, partial exact optimization, and solution recombination, which consistently outperforms greedy and ensemble methods on both synthetic and real benchmark data, offering a practical tool for building compact, well-separated hierarchical clusterings.