ABAmbrogio Maria Bernardelli

Ambrogio Maria Bernardelli

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Ambrogio Maria Bernardelli has a total of 9 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    The cloven traveling salesman: cycle covers and the integrality gap of small ATSP instances

    by Alessandro Sosso, Ambrogio Maria Bernardelli, Stefano Gualandi

    This work proposes a novel enumeration algorithm for computing the integrality gap of small instances of the subtour elimination formulation for the Asymmetric Traveling Salesman Problem ( atsp ). The core idea is to enumerate pairs of cycle covers that can be filtered and mapped to half-integer vertices of the subtour elimination polytope. The two-cycle covers are encoded as lexicographically ordered partitions of n numbers, with an encoding that prevents the generation of several isomorphic vertices. However, since not every cycle cover pair can be mapped to a vertex of the subtour elimination polytope, we have designed an efficient property-checking procedure to control whether a given point is a vertex of the asymmetric subtour elimination polytope. The proposed approach turns upside down the algorithms presented in the literature that first generate every possible vertex and later filter isomorphic vertices. With our approach, we can replicate state-of-the-art results for $$n\le 9$$ in a tiny fraction of time, and we compute for the first time the exact integrality gap of half-integer vertices of the asymmetric subtour elimination polytope for $$n=10, 11, 12$$ .

  • Open Access

    The Cloven Traveling Salesman: Cycle Covers and the Integrality Gap of Small ATSP Instances

    by Alessandro Sosso, Ambrogio Maria Bernardelli, Stefano Gualandi

    This work proposes a novel enumeration algorithm for computing the integrality gap of small instances of the subtour elimination formulation for the Asymmetric Traveling Salesman Problem (ATSP). The core idea is to enumerate pairs of vertex-disjoint cycle covers that can be filtered and mapped to half-integer vertices of the subtour elimination polytope. The two-cycle covers are encoded as lexicographically ordered partitions of $n$ numbers, with an encoding that prevents the generation of several isomorphic vertices. However, since not every cycle cover pair can be mapped to a vertex of the subtour elimination polytope, we have designed an efficient property-checking procedure to control whether a given point is a vertex of the asymmetric subtour elimination polytope. The proposed approach turns upside down the algorithms presented in the literature that first generate every possible vertex and later filter isomorphic vertices. With our approach, we can replicate state-of-the-art results for n<=9 in a tiny fraction of time, and we compute for the first time the exact integrality gap of half-integer vertices of the asymmetric subtour elimination polytope for n=10, 11, 12.

  • Open Access

    Methods for combinatorial optimization and their applications

    by Ambrogio Maria Bernardelli

  • Multiobjective Linear Ensembles for Robust and Sparse Training of Few-Bit Neural Networks

    by Ambrogio Maria Bernardelli, Stefano Gualandi, Simone Milanesi, Hoong Chuin Lau, Neil Yorke-Smith

    Training neural networks (NNs) using combinatorial optimization solvers has gained attention in recent years. In low-data settings, the use of state-of-the-art mixed integer linear programming solvers, for instance, has the potential to exactly train an NN while avoiding computing-intensive training and hyperparameter tuning and simultaneously training and sparsifying the network. We study the case of few-bit discrete-valued neural networks, both binarized neural networks (BNNs) whose values are restricted to ±1 and integer-valued neural networks (INNs) whose values lie in the range [ ]. Few-bit NNs receive increasing recognition because of their lightweight architecture and ability to run on low-power devices: for example, being implemented using Boolean operations. This paper proposes new methods to improve the training of BNNs and INNs. Our contribution is a multiobjective ensemble approach based on training a single NN for each possible pair of classes and applying a majority voting scheme to predict the final output. Our approach results in the training of robust sparsified networks whose output is not affected by small perturbations on the input and whose number of active weights is as small as possible. We empirically compare this BeMi approach with the current state of the art in solver-based NN training and with traditional gradient-based training, focusing on BNN learning in few-shot contexts. We compare the benefits and drawbacks of INNs versus BNNs, bringing new light to the distribution of weights over the [ ] interval. Finally, we compare multiobjective versus single-objective training of INNs, showing that robustness and network simplicity can be acquired simultaneously, thus obtaining better test performances. Although the previous state-of-the-art approaches achieve an average accuracy of [ ] on the Modified National Institute of Standards and Technology data set, the BeMi ensemble approach achieves an average accuracy of 68.4% when trained with 10 images per class and 81.8% when trained with 40 images per class while having up to 75.3% NN links removed. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This research was partially supported by the European Union Horizon 2020 Research and Innovation Programme [Grant 952215]. The work of A. M. Bernardelli is supported by a PhD scholarship funded under the “Programma Operativo Nazionale Ricerca e Innovazione” 2014–2020. Supplemental Material: The software that supports the findings of this study is available within the paper as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0281 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

  • Code and Data Repository for Multi-Objective Linear Ensembles for Robust and Sparse Training of Few-Bit Neural Networks

    by Ambrogio Maria Bernardelli, Stefano Gualandi, Simone Milanesi, Hoong Chuin Lau, Neil Yorke-Smith

    The goal of this script is to train neural networks with integer weights with MILP models and to test their accuracy.

  • Open Access

    Multi-objective stochastic scheduling of inpatient and outpatient surgeries

    by Ambrogio Maria Bernardelli, Lorenzo Bonasera, Davide Duma, Eleonora Vercesi

    With the advancement of surgery and anesthesiology in recent years, surgical clinical pathways have changed significantly, with an increase in outpatient surgeries. However, the surgical scheduling problem is particularly challenging when inpatients and outpatients share the same operating room blocks, due to their different characteristics in terms of variability and preferences. In this paper, we present a two-phase stochastic optimization approach that takes into account such characteristics, considering multiple objectives and dealing with uncertainty in surgery duration, arrival of emergency patients, and no-shows. Chance Constrained Integer Programming and Stochastic Mixed Integer Programming are used to deal with the advance scheduling and the allocation scheduling, respectively. Since Monte Carlo sampling is inefficient for solving the allocation scheduling problem for large size instances, a genetic algorithm is proposed for sequencing and timing procedures. Finally, a quantitative analysis is performed to analyze the trade-off between schedule robustness and average performance under the selection of different patient mixes, providing general insights for operating room scheduling when dealing with inpatients, outpatient, and emergencies.


  • The BeMi Stardust: A Structured Ensemble of Binarized Neural Networks

    by Ambrogio Maria Bernardelli, Stefano Gualandi, Hoong Chuin Lau, Simone Milanesi


  • Open Access

    The BeMi Stardust: a Structured Ensemble of Binarized Neural Networks

    by Ambrogio Maria Bernardelli, Stefano Gualandi, Hoong Chuin Lau, Simone Milanesi

    Binarized Neural Networks (BNNs) are receiving increasing attention due to their lightweight architecture and ability to run on low-power devices. The state-of-the-art for training classification BNNs restricted to few-shot learning is based on a Mixed Integer Programming (MIP) approach. This paper proposes the BeMi ensemble, a structured architecture of BNNs based on training a single BNN for each possible pair of classes and applying a majority voting scheme to predict the final output. The training of a single BNN discriminating between two classes is achieved by a MIP model that optimizes a lexicographic multi-objective function according to robustness and simplicity principles. This approach results in training networks whose output is not affected by small perturbations on the input and whose number of active weights is as small as possible, while good accuracy is preserved. We computationally validate our model using the MNIST and Fashion-MNIST datasets using up to 40 training images per class. Our structured ensemble outperforms both BNNs trained by stochastic gradient descent and state-of-the-art MIP-based approaches. While the previous approaches achieve an average accuracy of 51.1% on the MNIST dataset, the BeMi ensemble achieves an average accuracy of 61.7% when trained with 10 images per class and 76.4% when trained with 40 images per class.