submodularity

Strong formulations for quadratic optimization with M-matrices and semi-continuous variables

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

    We study quadratic optimization with semi-continuous variables and an M-matrix, i.e., PSD with non-positive off-diagonal entries. This structure arises in image segmentation, portfolio optimization, as well as a substructure of general quadratic optimization problems. We prove, under mild assumptions, that the minimization problem is solvable in polynomial time by showing its equivalence to a submodular … Read more

    Lifted Polymatroid Inequalities for Mean-Risk Optimization with Indicator Variables

  • Alper Atamturk
  • Hyemin Jeon
    • Categories (Mixed) Integer Nonlinear Programming, Stochastic Programming Tags , , , ,

    We investigate a mixed 0-1 conic quadratic optimization problem with indicator variables arising in mean-risk optimization. The indicator variables are often used to model non-convexities such as fixed charges or cardinality constraints. Observing that the problem reduces to a submodular function minimization for its binary restriction, we derive three classes of strong convex valid inequalities … Read more

    Path Cover and Path Pack Inequalities for the Capacitated Fixed-Charge Network Flow Problem

  • Alper Atamturk
  • Simge Küçükyavuz
  • Birce Tezel
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , , ,

    Capacitated fixed-charge network flows are used to model a variety of problems in telecommunication, facility location, production planning and supply chain management. In this paper, we investigate capacitated path substructures and derive strong and easy-to-compute path cover and path pack inequalities. These inequalities are based on an explicit characterization of the submodular inequalities through a … Read more

    Maximizing a class of utility functions over the vertices of a polytope

  • Alper Atamturk
  • Andrés Gómez
    • Categories (Mixed) Integer Nonlinear Programming, Robust Optimization, Stochastic Programming Tags , , , , , , , ,

    Given a polytope X, a monotone concave univariate function g, and two vectors c and d, we study the discrete optimization problem of finding a vertex of X that maximizes the utility function c’x + g(d’x). This problem has numerous applications in combinatorial optimization with a probabilistic objective, including estimation of project duration with stochastic … Read more

    Combinatorial Optimal Control of Semilinear Elliptic PDEs

  • Christoph Buchheim
  • Renke Kuhlmann
  • Christian Meyer
    • Categories Cutting Plane Approaches, Semi-infinite Programming, Systems governed by Differential Equations Optimization Tags , , , ,

    Optimal control problems (OCP) containing both integrality and partial differential equation (PDE) constraints are very challenging in practice. The most wide-spread solution approach is to first discretize the problem, it results in huge and typically nonconvex mixed-integer optimization problems that can be solved to proven optimality only in very small dimensions. In this paper, we … Read more

    Maximizing a class of submodular utility functions with constraints

  • Shabbir Ahmed
  • Jiajin Yu
    • Categories 0-1 Programming, Cutting Plane Approaches, Stochastic Programming Tags , , , ,

    Motivated by stochastic 0-1 integer programming problems with an expected utility objective, we study the mixed-integer nonlinear set: $P = \cset{(w,x)\in \reals \times \set{0,1}^N}{w \leq f(a’x + d), b’x \leq B}$ where $N$ is a positive integer, $f:\reals \mapsto \reals$ is a concave function, $a, b \in \reals^N$ are nonnegative vectors, $d$ is a real … Read more

    Maximizing expected utility over a knapsack constraint

  • Shabbir Ahmed
  • Jiajin Yu
    • Categories Approximation Algorithms, Integer Programming, Stochastic Programming Tags , , , ,

    The expected utility knapsack problem is to pick a set of items whose values are described by random variables so as to maximize the expected utility of the total value of the items picked while satisfying a constraint on the total weight of items picked. We consider the following solution approach for this problem: (i) … Read more

    Inclusion Certificates and Simultaneous Convexification of Functions

  • Mohit Tawarmalani
    • Categories (Mixed) Integer Nonlinear Programming, 0-1 Programming, Global Optimization Theory Tags , , ,

    We define the inclusion certificate as a measure that expresses each point in the domain of a collection of functions as a convex combination of other points in the domain. Using inclusion certificates, we extend the convex extensions theory to enable simultaneous convexification of functions. We discuss conditions under which the domain of the functions … Read more