AGAkshay Gupte

Akshay Gupte

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Akshay Gupte has a total of 30 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Correction: Edge expansion of a graph: SDP-based computational strategies

    by Akshay Gupte, Melanie Siebenhofer, Angelika Wiegele


  • Spatial Branch-and-Bound for Nonconvex Separable Piecewise Linear Optimization

    by Thomas Hübner, Akshay Gupte, Steffen Rebennack

    Nonconvex separable piecewise linear functions (PLFs) frequently appear in applications and to approximate nonlinearitites. The standard practice to formulate nonconvex PLFs is from the perspective of discrete optimization using special ordered sets and mixed-integer linear programs (MILPs). In contrast, we take the viewpoint of global continuous optimization and present a spatial branch-and-bound algorithm for optimizing a separable discontinuous PLF over a closed convex set. It offers slim and sparse linear programming relaxations, sharpness throughout the search tree, and an increased flexibility in branching decisions. The main feature of our algorithm is the generation of convex underestimators at the root node of the search tree and their quick and efficient updates at each node after branching. Convergence to the global optimum is achieved when the PLFs are lower semicontinuous. A Python implementation of our algorithm is tested on knapsack and network flow problems for both continuous and discontinuous PLFs. Our algorithm is compared with four logarithmic MILP formulations solved by Gurobi’s MILP solver as well as Gurobi’s PLF solver. We also compare our method against mixed-integer nonlinear program formulations solved by Gurobi. The numerical experiments indicate significant performance gains up to two orders of magnitude for medium- to large-sized PLFs. Finally, we also give an upper bound on the additive error from PLF approximations of nonconvex separable optimization. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: The research of S. Rebennack is supported by the Deutsche Forschungsgemeinschaft [Grant 445857709]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0755 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0755 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .


  • Open Access

    Edge expansion of a graph: SDP-based computational strategies

    by Akshay Gupte, Melanie Siebenhofer, Angelika Wiegele

    Computing the edge expansion of a graph is a famously hard combinatorial problem for which there have been many approximation studies. We present two variants of exact algorithms using semidefinite programming (SDP) to compute this constant for any graph. The first variant uses the SDP relaxation first to reduce the search space considerably. The problem is then transformed into instances of max-cut problems which are solved with an SDP-based state-of-the-art solver. Our second variant to compute the edge expansion uses Dinkelbach’s algorithm for fractional programming. This is, we have to solve a parametrized optimization problem and again we use semidefinite programming to obtain solutions of the parametrized problems. Numerical results demonstrate that with our algorithms one can compute the edge expansion on graphs up to 400 vertices in a routine way, including instances where standard branch-and-cut solvers fail. To the best of our knowledge, these are the first SDP-based solvers for computing the edge expansion of a graph.


  • Large Independent Sets in Recursive Markov Random Graphs

    by Akshay Gupte, Yiran Zhu

    Computing the maximum size of an independent set in a graph is a famously hard combinatorial problem that has been well studied for various classes of graphs. When it comes to random graphs, the classic Erdős–Rényi–Gilbert random graph [ ] has been analyzed and shown to have the largest independent sets of size [ ] with high probability (w.h.p.) This classic model does not capture any dependency structure between edges that can appear in real-world networks. We define random graphs [ ] whose existence of edges is determined by a Markov process that is also governed by a decay parameter [ ]. We prove that w.h.p. [ ] has independent sets of size [ ] for arbitrary [ ]. This is derived using bounds on the terms of a harmonic series, a Turán bound on a stability number, and a concentration analysis for a certain sequence of dependent Bernoulli variables that may also be of independent interest. Because [ ] collapses to [ ] when there is no decay, it follows that having even the slightest bit of dependency (any [ ]) in the random graph construction leads to the presence of large independent sets, and thus, our random model has a phase transition at its boundary value of r = 1. This implies that there are large matchings in the line graph of [ ], which is a Markov random field. For the maximal independent set output by a greedy algorithm, we deduce that it has a performance ratio of at most [ ] w.h.p. when the lowest degree vertex is picked at each iteration and also show that, under any other permutation of vertices, the algorithm outputs a set of size [ ], where [ ] and, hence, has a performance ratio of [ ]. Funding: The initial phase of this research was supported by the National Science Foundation [Grant DMS-1913294].

  • Code and Data Repository for Spatial Branch-and-Bound for Nonconvex Separable Piecewise Linear Optimization

    by Thomas Hübner, Akshay Gupte, Steffen Rebennack

    This repository contains the code used to conduct the computational experiments described in the paper Spatial branch-and-bound for nonconvex separable piecewise-linear optimization.


  • Open Access

    Computing the Edge Expansion of a Graph Using Semidefinite Programming

    by Akshay Gupte, Melanie Siebenhofer, Angelika Wiegele

    Computing the edge expansion of a graph is a famously hard combinatorial problem for which there have been many approximation studies. We present two versions of an exact algorithm using semidefinite programming (SDP) to compute this constant for any graph. The SDP relaxation is used to first reduce the search space considerably. One version applies then an SDP-based branch-and-bound algorithm, along with heuristic search. The other version transforms the problem into an instance of a max-cut problem and solves this using a state-of-the-art solver. Numerical results demonstrate that we clearly outperform mixed-integer quadratic solvers as well as another SDP-based algorithm from the literature.


  • Open Access

    Multilinear formulations for computing Nash equilibrium of multi-player matrix games

    by Miriam Fischer, Akshay Gupte

    We present multilinear and mixed-integer multilinear programs to find a Nash equilibrium in multi-player noncooperative games. We compare the formulations to common algorithms in Gambit, and conclude that a multilinear feasibility program finds a Nash equilibrium faster than any of the methods we compare it to, including the quantal response equilibrium method, which is recommended for large games. Hence, the multilinear feasibility program is an alternative method to find a Nash equilibrium in multi-player games, and outperforms many common algorithms. The mixed-integer formulations are generalisations of known mixed-integer programs for two-player games, however unlike two-player games, these mixed-integer programs do not give better performance than existing algorithms.

  • Open Access

    Large independent sets in recursive Markov random graphs

    by Akshay Gupte, Yiran Zhu

    Computing the maximum size of an independent set in a graph is a famously hard combinatorial problem that has been well-studied for various classes of graphs. When it comes to random graphs, only the classical binomial random graph $G_{n,p}$ has been analysed and shown to have largest independent sets of size $\Theta(\log{n})$ w.h.p. This classical model does not capture any dependency structure between edges that can appear in real-world networks. We initiate study in this direction by defining random graphs $G^{r}_{n,p}$ whose existence of edges is determined by a Markov process that is also governed by a decay parameter $r\in(0,1]$. We prove that w.h.p. $G^{r}_{n,p}$ has independent sets of size $(\frac{1-r}{2+\epsilon}) \frac{n}{\log{n}}$ for arbitrary $\epsilon > 0$, which implies an asymptotic lower bound of $\Omega(\pi(n))$ where $\pi(n)$ is the prime-counting function. This is derived using bounds on the terms of a harmonic series, Tur\'an bound on stability number, and a concentration analysis for a certain sequence of dependent Bernoulli variables that may also be of independent interest. Since $G^{r}_{n,p}$ collapses to $G_{n,p}$ when there is no decay, it follows that having even the slightest bit of dependency (any $r < 1$) in the random graph construction leads to the presence of large independent sets and thus our random model has a phase transition at its boundary value of $r=1$. For the maximal independent set output by a greedy algorithm, we deduce that it has a performance ratio of at most $1 + \frac{\log{n}}{(1-r)}$ w.h.p. when the lowest degree vertex is picked at each iteration, and also show that under any other permutation of vertices the algorithm outputs a set of size $\Omega(n^{1/1+\tau})$, where $\tau=1/(1-r)$, and hence has a performance ratio of $O(n^{\frac{1}{2-r}})$.

  • Open Access

    On strong duality, theorems of the alternative, and projections in conic optimization

    by Temitayo Ajayi, Akshay Gupte, Amin Khademi, Andrew Schaefer

    A conic program is the problem of optimizing a linear function over a closed convex cone intersected with an affine preimage of another cone. We analyse three constraint qualifications, namely a Closedness CQ, Slater CQ, and Boundedness CQ (also called Clark-Duffin theorem), that are sufficient for achieving strong duality and show that the first implies the second which implies the third, and also give a more general form of the third CQ for conic problems. Furthermore, two consequences of strong duality are presented, the first being a theorem of the alternative on almost feasibility (also called weak infeasibility), and the second being an explicit description of the projection of conic sets onto linear subspaces, akin to using projection cones for polyhedral sets.

  • Open Access

    Polyhedral Analysis of Symmetric Multilinear Polynomials over Box Constraints

    by Yibo Xu, Warren Adams, Akshay Gupte

    It is well-known that the convex and concave envelope of a multilinear polynomial over a box are polyhedral functions. Exponential-sized extended and projected formulations for these envelopes are also known. We consider the convexification question for multilinear polynomials that are symmetric with respect to permutations of variables. Such a permutation-invariant structure naturally implies a quadratic-sized extended formulation for the envelopes through the use of disjunctive programming. The optimization and separation problems are answered directly without using this extension. The problem symmetry allows the optimization and separation problems to be answered directly without using any extension. It also implies that permuting the coefficients of a core set of facets generates all the facets. We provide some necessary conditions and some sufficient conditions for a valid inequality to be a core facet. These conditions are applied to obtain envelopes for two classes: symmetric supermodular functions and multilinear monomials with reflection symmetry, thereby yielding alternate proofs to the literature. Furthermore, we use constructs from the reformulation-linearization-technique to completely characterize the set of points lying on each facet.