MMMonaldo Mastrolilli

Monaldo Mastrolilli

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

Monaldo Mastrolilli has a total of 85 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • The Falsification Problem: How Hard Is It to Falsify Heuristics?

    by Stefano Huber, Monaldo Mastrolilli, Eleonora Vercesi

  • Branch-and-Bound Algorithms as Polynomial-Time Approximation Schemes

    by Koppány István Encz, Monaldo Mastrolilli, Eleonora Vercesi

    Branch-and-bound algorithms (B&B) and polynomial-time approximation schemes (PTAS) are two seemingly distant areas of combinatorial optimization. We intend to (partially) bridge the gap between them while expanding the boundary of theoretical knowledge on the B&B framework. Branch-and-bound algorithms typically guarantee that an optimal solution is eventually found. However, we show that the standard implementation of branch-and-bound for certain knapsack and scheduling problems also exhibits PTAS-like behavior, yielding increasingly better solutions within polynomial time. Our findings are supported by computational experiments and comparisons with benchmark methods. Funding: This work was supported by Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung [Grant 200021_212929/1 (“Computational methods for integrality gaps analysis”)].

  • Open Access

    On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations

    by Alex Bortolotti, Monaldo Mastrolilli, Marilena Palomba, Luis Felipe Vargas

    The Sum-of-Squares (SoS) hierarchy is a powerful framework for polynomial optimization and proof complexity, offering tight semidefinite relaxations that capture many classical algorithms. Despite its broad applicability, several works have revealed fundamental limitations to SoS automatability. (i) While low-degree SoS proofs are often desirable for tractability, recent works have revealed they may require coefficients of prohibitively large bit size, rendering them computationally infeasible. (ii) Prior works have shown that SoS proofs for seemingly easy problems require high-degree. In particular, this phenomenon also arises in highly symmetric problems. Instances of symmetric problems-particularly those with a small number of constraints-have repeatedly served as benchmarks for establishing high-degree lower bounds in the SoS hierarchy. It has remained unclear whether symmetry can also lead to large bit sizes in SoS proofs, potentially making low-degree proofs computationally infeasible even in symmetric settings. In this work, we resolve this question by proving that symmetry alone does not lead to large bit size SoS proofs. Focusing on symmetric Archimedean instances, we show that low-degree SoS proofs for such systems admit compact, low bit size representations. Together, these results provide a conceptual separation between two sources of SoS hardness-degree and bit size-by showing they do not necessarily align, even in highly symmetric instances. This insight guides future work on automatability and lower bounds: symmetry may necessitate high-degree proofs, but it does not by itself force large coefficients.


  • Open Access

    On the integrality Gap of Small Asymmetric Traveling Salesman Problems: A Polyhedral and Computational Approach

    by Eleonora Vercesi, Janos Barta, Luca Maria Gambardella, Stefano Gualandi, Monaldo Mastrolilli

    In this paper, we investigate the integrality gap of the Asymmetric Traveling Salesman Problem (ATSP) with respect to the linear relaxation given by the Asymmetric Subtour Elimination Problem (ASEP) for instances with $n$ nodes, where $n$ is small. In particular, we focus on the geometric properties and symmetries of the ASEP polytope ($P^{n}_{ASEP}$) and its vertices. The polytope's symmetries are exploited to design a heuristic pivoting algorithm to search vertices where the integrality gap is maximized. Furthermore, a general procedure for the extension of vertices from $P^{n}_{ASEP}$ to $P^{n + 1}_{ASEP}$ is defined. The generated vertices improve the known lower bounds of the integrality gap for $ 16 \leq n \leq 22$ and, provide small hard-to-solve ATSP instances.

  • Open Access

    On the Degree Automatability of Sum-of-Squares Proofs

    by Alex Bortolotti, Monaldo Mastrolilli, Luis Felipe Vargas

    The Sum-of-Squares (SoS) hierarchy, also known as Lasserre hierarchy, has emerged as a promising tool in optimization. However, it remains unclear whether fixed-degree SoS proofs can be automated [O'Donnell (2017)]. Indeed, there are examples of polynomial systems with bounded coefficients that admit low-degree SoS proofs, but these proofs necessarily involve numbers with an exponential number of bits, implying that low-degree SoS proofs cannot always be found efficiently. A sufficient condition derived from the Nullstellensatz proof system [Raghavendra and Weitz (2017)] identifies cases where bit complexity issues can be circumvented. One of the main problems left open by Raghavendra and Weitz is proving any result for refutations, as their condition applies only to polynomial systems with a large set of solutions. In this work, we broaden the class of polynomial systems for which degree-$d$ SoS proofs can be automated. To achieve this, we develop a new criterion and we demonstrate how our criterion applies to polynomial systems beyond the scope of Raghavendra and Weitz's result. In particular, we establish a separation for instances arising from Constraint Satisfaction Problems (CSPs). Moreover, our result extends to refutations, establishing that polynomial-time refutation is possible for broad classes of polynomial time solvable constraint problems, highlighting a first advancement in this area.


  • Ideal Membership Problem for Boolean Minority and Dual Discriminator

    by Arpitha P. Bharathi, Monaldo Mastrolilli

    We consider the polynomial ideal membership problem (IMP) for ideals encoding combinatorial problems that are instances of constraint satisfaction problems over a finite language. In this paper, the input polynomial [Formula: see text] has degree at most [Formula: see text] (we call this problem IMP[Formula: see text]). We bridge the gap in [M. Mastrolilli, The complexity of the ideal membership problem for constrained problems over the Boolean domain, in SODA ’19, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA, Society for Industrial and Applied Mathematics, 2019, pp. 456–475] by proving that the IMP[Formula: see text] for Boolean combinatorial ideals whose constraints are closed under the minority polymorphism can be solved in polynomial time. This completes the identification of the tractability for the Boolean [Formula: see text]. We also prove that the proof of membership for the [Formula: see text] for problems constrained by the dual discriminator polymorphism over any finite domain can be found in polynomial time. Our results can be used in applications such as Nullstellensatz and sum-of-squares proofs.


  • Open Access

    Computational complexity of sum-of-squares bounds for copositive programs

    by Marilena Palomba, Lucas Slot, Luis Felipe Vargas, Monaldo Mastrolilli

    In recent years, copositive programming has received significant attention for its ability to model hard problems in both discrete and continuous optimization. Several relaxations of copositive programs based on semidefinite programming (SDP) have been proposed in the literature, meant to provide tractable bounds. However, while these SDP-based relaxations are amenable to the ellipsoid algorithm and interior point methods, it is not immediately obvious that they can be solved in polynomial time (even approximately). In this paper, we consider the sum-of-squares (SOS) hierarchies of relaxations for copositive programs introduced by Parrilo (2000), de Klerk & Pasechnik (2002) and Peña, Vera & Zuluaga (2006), which can be formulated as SDPs. We establish sufficient conditions that guarantee the polynomial-time computability (up to fixed precision) of these relaxations. These conditions are satisfied by copositive programs that represent standard quadratic programs and their reciprocals. As an application, we show that the SOS bounds for the (weighted) stability number of a graph can be computed efficiently. Additionally, we provide pathological examples of copositive programs (that do not satisfy the sufficient conditions) whose SOS relaxations admit only feasible solutions of doubly-exponential size.

  • Open Access

    Ideal Membership Problem for Boolean Minority and Dual Discriminator

    by Arpitha P. Bharathi, Monaldo Mastrolilli

    We consider the polynomial Ideal Membership Problem (IMP) for ideals encoding combinatorial problems that are instances of CSPs over a finite language. In this paper, the input polynomial $f$ has degree at most $d=O(1)$ (we call this problem IMP$_d$). We bridge the gap in \cite{MonaldoMastrolilli2019} by proving that the IMP$_d$ for Boolean combinatorial ideals whose constraints are closed under the minority polymorphism can be solved in polynomial time. This completes the identification of the tractability for the Boolean IMP$_d$. We also prove that the proof of membership for the IMP$_d$ for problems constrained by the dual discriminator polymorphism over any finite domain can be found in polynomial time. Our results can be used in applications such as Nullstellensatz and Sum-of-Squares proofs.

  • Open Access

    Tight Sum-of-squares Lower Bounds for Binary Polynomial Optimization Problems

    by Adam Kurpisz, Samuli Leppänen, Monaldo Mastrolilli

    For binary polynomial optimization problems of degree 2d with n variables Sakaue, Takeda, Kim, and Ito [ 33 ] proved that the \(\lceil \frac{n+2d-1}{2}\rceil\) th semidefinite (SDP) relaxation in the SoS/Lasserre hierarchy of SDP relaxations provides the exact optimal value. When n is an odd number, we show that their analysis is tight, i.e., we prove that \(\frac{n+2d-1}{2}\) levels of the SoS/Lasserre hierarchy are also necessary. Laurent [ 24 ] showed that the Sherali-Adams hierarchy requires n levels to detect the empty integer hull of a linear representation of a set with no integral points. She conjectured that the SoS/Lasserre rank for the same problem is n -1. In this article, we disprove this conjecture and derive lower and upper bounds for the rank.