Sanjeeb Dash

Evolving Scientific Discovery by Unifying Data and Background Knowledge with AI Hilbert

  • Ryan Cory-Wright
  • Cristina Cornelio
  • Sanjeeb Dash
  • Bachir El Khadir
  • Lior Horesh
    • Categories Basic Sciences Applications, Global Optimization Applications, Semi-definite Programming Tags , , ,

    The discovery of scientific formulae that parsimoniously explain natural phenomena and align with existing background theory is a key goal in science. Historically, scientists have derived natural laws by manipulating equations based on existing knowledge, forming new equations, and verifying them experimentally. In recent years, data-driven scientific discovery has emerged as a viable competitor in … Read more

    On Polytopes with Linear Rank with respect to Generalizations of the Split Closure

  • Sanjeeb Dash
  • Yatharth Dubey
    • Categories Cutting Plane Approaches, Polyhedra Tags , , , ,

    In this paper we study the rank of polytopes contained in the 0-1 cube with respect to $t$-branch split cuts and $t$-dimensional lattice cuts for a fixed positive integer $t$. These inequalities are the same as split cuts when $t=1$ and generalize split cuts when $t > 1$. For polytopes contained in the $n$-dimensional 0-1 … Read more

    Multilinear Sets with Two Monomials and Cardinality Constraints

  • Rui Chen
  • Sanjeeb Dash
  • Oktay Gunluk
    • Categories 0-1 Programming, Cutting Plane Approaches Tags , ,

    Binary polynomial optimization is equivalent to the problem of minimizing a linear function over the intersection of the multilinear set with a polyhedron. Many families of valid inequalities for the multilinear set are available in the literature, though giving a polyhedral characterization of the convex hull is not tractable in general as binary polynomial optimization … Read more

    Convexifying Multilinear Sets with Cardinality Constraints: Structural Properties, Nested Case and Extensions

  • Rui Chen
  • Sanjeeb Dash
  • Oktay Gunluk
    • Categories 0-1 Programming, Cutting Plane Approaches Tags , ,

    The problem of minimizing a multilinear function of binary variables is a well-studied NP-hard problem. The set of solutions of the standard linearization of this problem is called the multilinear set. We study a cardinality constrained version of it with upper and lower bounds on the number of nonzero variables. We call the set of … Read more

    On a generalization of the Chvatal-Gomory closure

  • Sanjeeb Dash
  • Oktay Gunluk
  • Dabeen Lee
    • Categories Cutting Plane Approaches, Integer Programming Tags , , , , ,

    Many practical integer programming problems involve variables with one or two-sided bounds. Dunkel and Schulz (2012) considered a strengthened version of Chvatal-Gomory (CG) inequalities that use 0-1 bounds on variables, and showed that the set of points in a rational polytope that satisfy all these strengthened inequalities is a polytope. Recently, we generalized this result … Read more

    Generalized Chvatal-Gomory closures for integer programs with bounds on variables

  • Sanjeeb Dash
  • Oktay Gunluk
  • Dabeen Lee
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , , ,

    Integer programming problems that arise in practice often involve decision variables with one or two sided bounds. In this paper, we consider a generalization of Chvatal-Gomory inequalities obtained by strengthening Chvatal-Gomory inequalities using the bounds on the variables. We prove that the closure of a rational polyhedron obtained after applying the generalized Chvatal-Gomory inequalities is … Read more

    Binary Extended Formulations of Polyhedral Mixed-integer Sets

  • Sanjeeb Dash
  • Oktay Gunluk
  • Robert Hildebrand
    • Categories 0-1 Programming, Cutting Plane Approaches, Integer Programming Tags , , ,

    We analyze different ways of constructing binary extended formulations of polyhedral mixed-integer sets with bounded integer variables and compare their relative strength with respect to split cuts. We show that among all binary extended formulations where each bounded integer variable is represented by a distinct collection of binary variables, what we call “unimodular” extended formulations … Read more

    Lattice closures of polyhedra

  • Sanjeeb Dash
  • Oktay Gunluk
  • Diego Moran
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , , , ,

    Given $P\subset\R^n$, a mixed-integer set $P^I=P\cap (\Z^{t}\times\R^{n-t}$), and a $k$-tuple of $n$-dimensional integral vectors $(\pi_1, \ldots, \pi_k)$ where the last $n-t$ entries of each vector is zero, we consider the relaxation of $P^I$ obtained by taking the convex hull of points $x$ in $P$ for which $ \pi_1^Tx,\ldots,\pi^T_kx$ are integral. We then define the $k$-dimensional … Read more

    On the polyhedrality of closures of multi-branch split sets and other polyhedra with bounded max-facet-width

  • Sanjeeb Dash
  • Oktay Gunluk
  • Diego Moran
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    For a fixed integer $t > 0$, we say that a $t$-branch split set (the union of $t$ split sets) is dominated by another one on a polyhedron $P$ if all cuts for $P$ obtained from the first $t$-branch split set are implied by cuts obtained from the second one. We prove that given a … Read more

    Optimization over Structured Subsets of Positive Semidefinite Matrices via Column Generation

  • Amir Ali Ahmadi
  • Sanjeeb Dash
  • Georgina Hall
    • Categories Approximation Algorithms, Linear, Cone and Semidefinite Programming, Nonlinear Optimization

    We develop algorithms for inner approximating the cone of positive semidefinite matrices via linear programming and second order cone programming. Starting with an initial linear algebraic approximation suggested recently by Ahmadi and Majumdar, we describe an iterative process through which our approximation is improved at every step. This is done using ideas from column generation … Read more