Ongoing projects

Ideal Membership Problems and the Bit Complexity of Sum of Squares Proofs

People: Alex Bortolotti, Marilena Palomba, Luis Felipe Vargas, Palmo Monaldo Mastrolilli

We investigate the fundamental limits of the Sum-of-Squares (SoS) hierarchy, focusing on its bit complexity and computational feasibility. Our research tackles key open problems in SoS proof efficiency, particularly in combinatorial optimization and constraint satisfaction. By linking SoS with Ideal Membership Problems (IMP) and techniques from algebra, SDP, and combinatorial optimization, we aim to establish precise tractability criteria.

Supported by: Swiss National Science Foundation project n. 200021_207429 / 1

Computational Methods for Integrality Gaps Analysis

People: Koppány István Encz, Stefano Huber, Tullio Villa, Eleonora Vercesi, Palmo Monaldo Mastrolilli, Luca Maria Gambardella

We explore a novel approach to benchmarking optimization algorithms by automatically generating hard problem instances that challenge their efficiency. Instead of relying solely on standard test sets, our research focuses on leveraging the integrality gap to construct computationally difficult instances for problems like the Travelling Salesman Problem and Tree Augmentation Problem. Combining insights from approximation theory, heuristic search, and operational research, we aim to develop a systematic methodology for evaluating algorithmic strengths and weaknesses.

Supported by: Swiss National Science Foundation project n. 200021_212929 / 1

Publications

  • The Integrality Gap of the Traveling Salesman Problem is 4/3 if the LP Solution Has at Most n+6 Non-Zero Components
    T. Villa, E. Vercesi, J. Barta, M. Mastrolilli
    2026, Integer Programming and Combinatorial Optimization, forthcoming. Preprint available on arXiv.

  • On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations
    A. Bortolotti, M. Mastrolilli, M. Palomba, L. F. Vargas
    2025, SIAM Journal on Discrete Mathematics, forthcoming. Preprint available on arXiv.

  • On the integrality gap of small Asymmetric Traveling Salesman Problems: A polyhedral and computational approach
    E. Vercesi, J. Barta, L. M. Gambardella, S. Gualandi, M. Mastrolilli
    2025, Discrete Optimization, vol. 57. Paper available on Science Direct.

  • Branch-and-Bound Algorithms as Polynomial-time Approximation Schemes
    K. I. Encz, M. Mastrolilli, E. Vercesi
    2025, 52nd International Colloquium on Automata, Languages, and Programming. Paper available on Dagstuhl Publishing.

  • On the Degree Automatability of Sum-of-Squares Proofs
    A. Bortolotti, M. Mastrolilli, L. F. Vargas
    2025, 52nd International Colloquium on Automata, Languages, and Programming. Paper available on Dagstuhl Publishing.

  • Computational Complexity of Sum-of-Squares Bounds for Copositive Programs
    M. Palomba, L. Slot, L. F. Vargas, M. Mastrolilli
    2025, SIAM Journal on Optimization, vol. 35, n. 4, pp. 2684-2711. Paper available on SIAM Publications.

  • Lower bounds for the integrality gap of the bi-directed cut formulation of the Steiner Tree Problem
    A. M. Bernardelli, E. Vercesi, S. Gualandi, M. Mastrolilli, L. M. Gambardella
    2025, [PREPRINT]. Preprint available on arXiv.

  • The Dantzig-Fulkerson-Johnson TSP formulation is easy to solve for few subtour constraints
    E. Vercesi, A. Buchanan
    [PREPRINT].

  • Copositive matrices, sums of squares and the stability number of a graph
    L. F. Vargas, M. Laurent
    2023, Polynomial Optimization, Moments, and Applications, pp. 113-151. Paper available on Springer Nature.

  • On the generation of metric TSP instances with a large integrality gap by branch-and-cut
    E. Vercesi, S. Gualandi, M. Mastrolilli, L. M. Gambardella
    2023, Mathematical Programming Computation, vol.15, pp. 389-416. Paper available on Springer Nature.