8 citations · 18 across the 25 of their papers we have counts for
23 papers · 1 filter
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…
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…
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…
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…
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…
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…
Minimizing Cubic and Homogeneous Polynomials over Integers in the Plane
Alberto Del Pia, Robert Hildebrand, Robert Weismantel +1
We complete the complexity classification by degree of minimizing a polynomial over the integer points in a polyhedron in . Previous work shows that optimizing a quad…
Reverse Split Rank
Michele Conforti, Alberto Del Pia, Marco Di Summa +1
The reverse split rank of an integral polyhedron P is defined as the supremum of the split ranks of all rational polyhedra whose integer hull is P. Already in R^3 there exist polyh…
Reverse Chvátal-Gomory rank
Michele Conforti, Alberto Del Pia, Marco Di Summa +2
We introduce the reverse Chvátal-Gomory rank r*(P) of an integral polyhedron P, defined as the supremum of the Chvátal-Gomory ranks of all rational polyhedra whose integer hull is…
A probabilistic comparison of the strength of split, triangle, and quadrilateral cuts (extended version)
Alberto Del Pia, Christian Wagner, Robert Weismantel
We consider mixed integer linear sets defined by two equations involving two integer variables and any number of non-negative continuous variables. The non-trivial valid inequaliti…