8 citations · 18 across the 25 of their papers we have counts for
31 papers
0/1 integer programming over polytopes of Chvátal rank one is as hard as lattice problems
Alberto Del Pia
A rational polyhedron has Chvátal rank at most one if a single round of Chvátal-Gomory cuts yields its integer hull. In 1973, Chvátal asked whether 0/1 integer programs over polyto…
Treewidth and the complexity of box-constrained quadratic programs
Alberto Del Pia, Aida Khajavirad
We consider the problem of minimizing a sparse quadratic function over the unit hypercube. In binary quadratic programming, treewidth of the interaction graph is a central paramete…
A quadratic upper bound on the Chvátal rank of polytopes in the 0/1-cube
Alberto Del Pia
We show that every polytope , and more generally every compact convex set, has Chvátal rank at most . This improves the b…
Rational Jacobi Rotations and the Complexity of Approximating Mixed Integer Quadratic Programming
Alberto Del Pia
We present an algorithm that finds an epsilon-approximate solution to a mixed integer quadratic programming (MIQP) problem, and that runs on a Turing machine in time polynomial in…
The complete edge relaxation for binary polynomial optimization
Alberto Del Pia, Aida Khajavirad
We consider the multilinear polytope, defined as the convex hull of the feasible region of a lifted binary polynomial optimization problem. We define a relaxation in an extended sp…
A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxation
Alberto Del Pia, Dekun Zhou
Sparse Principal Component Analysis (SPCA) is a fundamental technique for dimensionality reduction, and is NP-hard. In this paper, we introduce a randomized approximation algorithm…
Factorized binary polynomial optimization
Alberto Del Pia
In binary polynomial optimization, the goal is to find a binary point maximizing a given polynomial function. In this paper, we propose a novel way of formulating this general opti…
The Mixed Integer Trust Region Problem
Alberto Del Pia
In this paper we consider the problem of minimizing a general quadratic function over the mixed integer points in an ellipsoid. This problem is strongly NP-hard, NP-hard to approxi…
A Knowledge Compilation Take on Binary Polynomial Optimization
Florent Capelli, Alberto Del Pia, Silvia Di Gregorio
The Binary Polynomial Optimization (BPO) problem is defined as the problem of maximizing a given polynomial function over all binary points. The main contribution of this paper is…
Convex quadratic sets and the complexity of mixed integer convex quadratic programming
Alberto Del Pia
In pure integer linear programming it is often desirable to work with polyhedra that are full-dimensional, and it is well known that it is possible to reduce any polyhedron to a fu…
The pseudo-Boolean polytope and polynomial-size extended formulations for binary polynomial optimization
Alberto Del Pia, Aida Khajavirad
With the goal of obtaining strong relaxations for binary polynomial optimization problems, we introduce the pseudo-Boolean polytope defined as the convex hull of the set of binary…
A polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs
Alberto Del Pia, Aida Khajavirad
We consider the multilinear polytope defined as the convex hull of the set of binary points satisfying a collection of multilinear equations. The complexity of the facial structure…
Relaxations and Cutting Planes for Linear Programs with Complementarity Constraints
Alberto Del Pia, Jeff Linderoth, Haoran Zhu
We study relaxations for linear programs with complementarity constraints, especially instances whose complementary pairs of variables are not independent. Our formulation is based…
Clustering with Queries under Semi-Random Noise
Alberto Del Pia, Mingchen Ma, Christos Tzamos
The seminal paper by Mazumdar and Saha \cite{MS17a} introduced an extensive line of work on clustering with noisy queries. Yet, despite significant progress on the problem, the pro…
New Classes of Facets for Complementarity Knapsack Problems
Alberto Del Pia, Jeff Linderoth, Haoran Zhu
The complementarity knapsack problem (CKP) is a knapsack problem with real-valued variables and complementarity conditions between pairs of its variables. We extend the polyhedral…
An SDP Relaxation for the Sparse Integer Least Squares Problem
Alberto Del Pia, Dekun Zhou
In this paper, we study the \emph{sparse integer least squares problem} (SILS), an NP-hard variant of least squares with sparse -vectors. We propose an -based…
Rank-one Boolean tensor factorization and the multilinear polytope
Alberto Del Pia, Aida Khajavirad
We consider the NP-hard problem of finding the closest rank-one binary tensor to a given binary tensor, which we refer to as the rank-one Boolean tensor factorization (BTF) problem…
On the Complexity of Separating Cutting Planes for the Knapsack Polytope
Alberto Del Pia, Jeff Linderoth, Haoran Zhu
We close three open problems in the separation complexity of valid inequalities for the knapsack polytope. Specifically, we establish that the separation problems for extended cove…
K-median: exact recovery in the extended stochastic ball model
Alberto Del Pia, Mingchen Ma
We study exact recovery conditions for the linear programming relaxation of the k-median problem in the stochastic ball model (SBM). In Awasthi et al. (2015), the authors give a ti…
Multi-cover Inequalities for Totally-Ordered Multiple Knapsack Sets: Theory and Computation
Alberto Del Pia, Jeff Linderoth, Haoran Zhu
We propose a method to generate cutting-planes from multiple covers of knapsack constraints. The covers may come from different knapsack inequalities if the weights in the inequali…
Complexity, Exactness, and Rationality in Polynomial Optimization
Daniel Bienstock, Alberto del Pia, Robert Hildebrand
We focus on rational solutions or nearly-feasible rational solutions that serve as certificates of feasibility for polynomial optimization problems. We show that, under some separa…
On the complexity of binary polynomial optimization over acyclic hypergraphs
Alberto Del Pia, Silvia Di Gregorio
In this work we advance the understanding of the fundamental limits of computation for Binary Polynomial Optimization (BPO), which is the problem of maximizing a given polynomial f…
Linear Programming and Community Detection
Alberto Del Pia, Aida Khajavirad, Dmitriy Kunisky
The problem of community detection with two equal-sized communities is closely related to the minimum graph bisection problem over certain random graph models. In the stochastic bl…
Lower bounds on the lattice-free rank for packing and covering integer programs
Merve Bodur, Alberto Del Pia, Santanu S. Dey +1
In this paper, we present lower bounds on the rank of the split closure, the multi-branch closure and the lattice-free closure for packing sets as a function of the integrality gap…