Alberto Del Pia

Towards a geometric characterization of unbounded integer cubic optimization problems via thin rays

  • Alberto Del Pia
    • Categories (Mixed) Integer Nonlinear Programming

    We study geometric characterizations of unbounded integer polynomial optimization problems. While unboundedness along a ray fully characterizes unbounded integer linear and quadratic optimization problems, we show that this is not the case for cubic polynomials. To overcome this, we introduce thin rays, which are rays with an arbitrarily small neighborhood, and prove that they characterize … Read more

    Projection-width: a unifying structural parameter for separable discrete optimization

  • Alberto Del Pia
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, 0-1 Programming

    We introduce the notion of projection-width for systems of separable constraints, defined via branch decompositions of variables and constraints. We show that several fundamental discrete optimization and counting problems can be solved in polynomial time when the projection-width is polynomially bounded. These include optimization, counting, top-k, and weighted constraint violation. Our results identify a broad … Read more

    The complete edge relaxation for binary polynomial optimization

  • Alberto Del Pia
  • Aida Khajavirad
    • Categories 0-1 Programming, Global Optimization, Integer Programming Tags , , , , ,

    We consider the multilinear polytope defined as the convex hull of the feasible region of a linearized binary polynomial optimization problem. We define a relaxation in an extended space for this polytope, which we refer to as the complete edge relaxation. The complete edge relaxation is stronger than several well-known relaxations of the multilinear polytope, … Read more

    A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxation

  • Alberto Del Pia
  • Dekun Zhou
    • Categories (Mixed) Integer Linear Programming, Data Science Algorithms, Semi-definite Programming

    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 for SPCA, which is based on the basic SDP relaxation. Our algorithm has an approximation ratio of at most the sparsity constant with high probability, if called enough times. Under a … Read more

    Factorized binary polynomial optimization

  • Alberto Del Pia
    • Categories (Mixed) Integer Nonlinear Programming, 0-1 Programming, Integer Programming Tags , , , , ,

    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 optimization problem, which we call factorized binary polynomial optimization. In this formulation, we assume that the variables are partitioned into a fixed number of sets, and … Read more

    Relaxations and Cutting Planes for Linear Programs with Complementarity Constraints

  • Alberto Del Pia
  • Jeff Linderoth
  • Haoran Zhu
    • Categories 0-1 Programming, Cutting Plane Approaches, Global Optimization Tags , , , ,

    We study relaxations for linear programs with complementarity constraints, especially instances whose complementary pairs of variables are not independent. Our formulation is based on identifying vertex covers of the conflict graph of the instance and generalizes the extended reformulation-linearization technique of Nguyen, Richard, and Tawarmalani to instances with general complementarity conditions between variables. We demonstrate … Read more

    An SDP Relaxation for the Sparse Integer Least Squares Problem

  • Alberto Del Pia
  • Dekun Zhou
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Semi-definite Programming Tags , , , ,

    In this paper, we study the sparse integer least squares problem (SILS), an NP-hard variant of least squares with sparse {0, 1, -1}-vectors. We propose an l1-based SDP relaxation, and a randomized algorithm for SILS, which computes feasible solutions with high probability with an asymptotic approximation ratio 1/T^2 as long as the sparsity constant σ … Read more

    Rank-one Boolean tensor factorization and the multilinear polytope

  • Alberto Del Pia
  • Aida Khajavirad
    • Categories 0-1 Programming, Cutting Plane Approaches, Linear Programming Tags , , ,

    We consider the NP-hard problem of approximating a tensor with binary entries by a rank-one tensor, referred to as rank-one Boolean tensor factorization problem. We formulate this problem, in an extended space of variables, as the problem of minimizing a linear function over a highly structured multilinear set. Leveraging on our prior results regarding the … Read more