submodularity

On the Semidefinite Representability of Continuous Quadratic Submodular Minimization With Applications to Moment Problems

  • Samuel Burer
  • Karthik Natarajan
    • Categories Quadratic Programming, Robust Optimization, Semi-definite Programming Tags , ,

    We show that continuous quadratic submodular minimization with bounds is solvable in polynomial time using semidefinite programming, and we apply this result to two moment problems arising in distributionally robust optimization and the computation of covariance bounds. Accordingly, this research advances the ongoing study of continuous submodular minimization and opens new application areas therein. ArticleDownload … Read more

    Distributionally robust optimization through the lens of submodularity

  • Karthik Natarajan
  • Divya Padmanabhan
  • Arjun Ramachandra
    • Categories Convex Optimization, Linear Programming, Linear, Cone and Semidefinite Programming Tags , , , ,

    Distributionally robust optimization is used to solve decision making problems under adversarial uncertainty where the distribution of the uncertainty is itself ambiguous. In this paper, we identify a class of these instances that is solvable in polynomial time by viewing it through the lens of submodularity. We show that the sharpest upper bound on the … Read more

    Sequential Competitive Facility Location: Exact and Approximate Algorithms

  • Mingyao Qi
  • Ruiwei Jiang
  • Siqian Shen
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Facility Planning and Design Tags , , , , ,

    We study a competitive facility location problem (CFLP), where two firms sequentially open new facilities within their budgets, in order to maximize their market shares of demand that follows a probabilistic choice model. This process is a Stackelberg game and admits a bilevel mixed-integer nonlinear program (MINLP) formulation. We derive an equivalent, single-level MINLP reformulation … Read more

    Conic Mixed-Binary Sets: Convex Hull Characterizations and Applications

  • Fatma Kılınç-Karzan
  • Simge Küçükyavuz
  • Dabeen Lee
    • Categories (Mixed) Integer Nonlinear Programming Tags , , , , , , ,

    We consider a general conic mixed-binary set where each homogeneous conic constraint involves an affine function of independent continuous variables and an epigraph variable associated with a nonnegative function, $f_j$, of common binary variables. Sets of this form naturally arise as substructures in a number of applications including mean-risk optimization, chance-constrained problems, portfolio optimization, lot-sizing … Read more

    Constrained Assortment Optimization under the Paired Combinatorial Logit Model

  • Rohan Ghuge
  • Viswanath Nagarajan
  • Joseph Kwon
  • Adetee Sharma
    • Categories Applications - OR and Management Sciences Tags , ,

    We study the assortment optimization problem when customer choices are governed by the paired combinatorial logit model. We study unconstrained, capacitated and knapsack constrained versions of this problem, which are all known to be NP-hard. We design efficient algorithms that compute approximately optimal solutions, using a novel relation to the maximum directed cut problem and … Read more

    Submodularity in conic quadratic mixed 0-1 optimization

  • Alper Atamturk
  • Andrés Gómez
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches Tags , , , , , , ,

    We describe strong convex valid inequalities for conic quadratic mixed 0-1 optimization. These inequalities can be utilized for solving numerous practical nonlinear discrete optimization problems from value-at-risk minimization to queueing system design, from robust interdiction to assortment optimization through appropriate conic quadratic mixed 0-1 relaxations. The inequalities exploit the submodularity of the binary restrictions and … Read more

    Submodularity and valid inequalities in nonlinear optimization with indicator variables

  • Andrés Gómez
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches Tags , , ,

    We propose a new class of valid inequalities for mixed-integer nonlinear optimization problems with indicator variables. The inequalities are obtained by lifting polymatroid inequalities in the space of the 0–1 variables into conic inequalities in the original space of variables. The proposed inequalities are shown to describe the convex hull of the set under study … Read more

    A mixed-integer fractional optimization approach to best subset selection

  • Andrés Gómez
  • Oleg A. Prokopyev
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Statistics Tags , , ,

    We consider the best subset selection problem in linear regression, i.e., finding a parsimonious subset of the regression variables that provides the best fit to the data according to some predefined criterion. We show that, for a broad range of criteria used in the statistics literature, the best subset selection problem can be modeled as … Read more

    Multi-Product Newsvendor Problem with Customer-driven Demand Substitution: A Stochastic Integer Program Perspective

  • Jie Zhang
  • Weijun Xie
  • Subhash Sarin
    • Categories Applications - OR and Management Sciences Tags , , , ,

    This paper studies a multi-product newsvendor problem with customer-driven demand substitution, where each product, once run out of stock, can be proportionally substituted by the others. This problem has been widely studied in the literature, however, due to nonconvexity and intractability, only limited analytical properties have been reported and no efficient approaches have been proposed. … Read more

    Strong formulations for conic quadratic optimization with indicator variables

  • Andrés Gómez
    • Categories (Mixed) Integer Nonlinear Programming Tags , , ,

    We study the convex hull of the mixed-integer set given by a conic quadratic inequality and indicator variables. Conic quadratic terms are often used to encode uncertainties, while the indicator variables are used to model fixed costs or enforce sparsity in the solutions. We provide the convex hull description of the set under consideration when … Read more