Home Research Teaching Resumé Miscellaneous
The supermodular covering knapsack set is the discrete upper level set of a non-decreasing supermodular function. Submodular and supermodular knapsack sets arise naturally when modeling utilities, risk and probabilistic constraints on discrete variables. In a recent paper Atamtürk and Narayanan study the lower level set of a non-decreasing submodular function. In this complementary paper we describe pack inequalities for the supermodular covering knapsack set and investigate their separation, extensions and lifting. We give sequence-independent upper bounds and lower bounds on the lifting coefficients. Furthermore, we present a computational study on using the polyhedral results derived for solving 0-1 optimization problems over conic quadratic constraints with a branch-and-cut algorithm.
Spectrahedra are linear sections of the cone of positive semidefinite matrices which, as convex bodies, generalize the class of polyhedra. In this paper we investigate the problem of recognizing when a spectrahedron is polyhedral. We generalize and strengthen results of Ramana (1998) regarding the structure of spectrahedra and we devise a normal form of representations of spectrahedra. This normal form is effectively computable and leads to an algorithm for deciding polyhedrality. Our investigation was originally motivated by that if a spectrahedron can be recognized to be a polyhedron then the corresponding semidefinite program can be modeled as a linear program and solved rather efficiently. As Ramana (1998) describes, another motivation lies in connections between spectrahedra and perfect graph theory.
We consider a network design problem with random arc capacities and give a formulation with a probabilistic capacity constraint on each cut of the network. To handle the exponentially-many probabilistic constraints a separation procedure that solves a nonlinear minimum cut problem is introduced. For the case with independent arc capacities, we exploit the supermodularity of the set function defining the constraints and generate cutting planes based on the supermodular covering knapsack polytope. For the general correlated case, we give a reformulation of the constraints that allows to uncover and utilize the submodularity of a related function. The computational results indicate that exploiting the underlying submodularity and supermodularity arising with the probabilistic constraints provides significant advantages over the classical approaches.
Solving linear systems of equations is one of the most common operation in scientific computing. These applications frequently lead to solving very large dense set of linear equations, often with millions of rows and columns, and solving these problems is very time consuming. In this work we present a MATLAB implementation of the communication-avoiding LU factorization (CALU) algorithm for computing the LU factorization of a dense matrix A distributed in a two dimensional layout (Demmel and Gu, 2010). This version of CALU is based on a complete pivoting strategy, that we show is numerically stable in practice. Furthermore, we contrast the results thus obtained with classical pivoting schemes Gaussian Elimination with Partial Pivoting (GEPP) and Gaussian Elimination with Complete Pivoting (GECP). CALU has two main characteristics, first, it is latency avoiding, as it allows for a significant decrease in the number of messages exchanged during the factorization relative to conventional algorithms. Second, unlike conventional algorithms, CALU allows the usage of the best available sequential algorithms for computing the LU factorization of a block submatrix, as for example the recursive algorithms.
The Newsvendor model is one of the extensively studied models in the Operations Research Literature. The work in context tries to quantify and verify the model to emulate the real world supplies and demand, by mapping them to the binary lattice space. This mapping, in addition to providing an easier way to develop a theoretical understanding for the model, yields a computationally effective means to compute the optimal order quantities. We derive sufficient conditions for independence of the optimal order quantities and supply distributions. We establish unimodularity of the expected return function and explore the same to propose an algorithm to compute the optimal order quantity when supply and demand are dependent.
This work tries to develop an optimization model to determine the assortment and distribution of product units on the shelf that will maximize the ROI signifying the importance and involvement of various shelf space parameters specifically the cross-space elasticities of demand which are generally neglected. The mathematical model uses a multiplicative-algorithm and proposes a Pure Integer Non-Linear Programming Optimization model, highlighting the various aspects of the consumer demand, including stock-out considerations, and the effect of shelf level as well. The output from the model is the assortment constitution and quantity for each product in the assortment to be shelved. The work also incubates an insight into the area of allocation of shelf space to newly launched products, which has not been addressed anywhere in the literature. Dynamism of the consumer demand and thus shelf elasticities have been incorporated in the mathematical model to address the same. The motivation is drawn with respect to present scenarios where producers are continuously launching new products in their quest of acquiring larger market shares and this is where the retailing decisions can be crucial. Thus obliterating the philosophy, "new products can only crowd the already crowded shelf space". This work was presented at the 40th Annual Convention of the Operations Research Society of India, New Delhi (ORSI 2007).