4 citations · 5 across the 9 of their papers we have counts for
10 papers · 1 filter
A geometric characterization of unbounded integer cubic optimization problems via thin rays
Alberto Del Pia
We study geometric characterizations of unbounded integer polynomial optimization problems. Unboundedness along a ray characterizes unbounded integer linear and quadratic optimizat…
Projection-width as a structural parameter for discrete separable optimization
Alberto Del Pia
While several classes of integer linear optimization problems are known to be solvable in polynomial time, far fewer tractability results exist for integer nonlinear optimization.…
Extended formulations for the multilinear polytope of acyclic hypergraphs
Alberto Del Pia, Aida Khajavirad
This article provides an overview of our joint work on binary polynomial optimization over the past decade. We define the multilinear polytope as the convex hull of the feasible re…
Beyond hypergraph acyclicity: limits of tractability for pseudo-Boolean optimization
Alberto Del Pia, Aida Khajavirad
In this paper, we study the problem of minimizing a polynomial function with literals over all binary points, often referred to as pseudo-Boolean optimization. We investigate the f…
An Approximation Algorithm for Indefinite Mixed Integer Quadratic Programming
Alberto Del Pia
In this paper, we give an algorithm that finds an epsilon-approximate solution to a mixed integer quadratic programming (MIQP) problem. The algorithm runs in polynomial time if the…
Proximity in Concave Integer Quadratic Programming
Alberto Del Pia, Mingchen Ma
A classic result by Cook, Gerards, Schrijver, and Tardos provides an upper bound of on the proximity of optimal solutions of an Integer Linear Programming problem and its sta…
Integer packing sets form a well-quasi-ordering
Alberto Del Pia, Dion Gijswijt, Jeff Linderoth +1
An integer packing set is a set of non-negative integer vectors with the property that, if a vector is in the set, then every non-negative integer vector with is…
Subdeterminants and Concave Integer Quadratic Programming
Alberto Del Pia
We consider the NP-hard problem of minimizing a separable concave quadratic function over the integral points in a polyhedron, and we denote by D the largest absolute value of the…
Subset selection in sparse matrices
Alberto Del Pia, Santanu S. Dey, Robert Weismantel
In subset selection we search for the best linear predictor that involves a small subset of variables. From a computational complexity viewpoint, subset selection is NP-hard and fe…
On the convergence of the affine hull of the Chvátal-Gomory closures
Gennadiy Averkov, Michele Conforti, Alberto Del Pia +2
Given an integral polyhedron P and a rational polyhedron Q living in the same n-dimensional space and containing the same integer points as P, we investigate how many iterations of…