On the Complexity of Non-Overlapping Multivariate Marginal Bounds for Probabilistic Combinatorial Optimization Problems

  • Xuan Vinh Doan
  • Karthik Natarajan
    • Categories Combinatorial Optimization, Stochastic Programming Tags , ,

    Given a combinatorial optimization problem with an arbitrary partition of the set of random objective coefficients, we evaluate the tightest possible bound on the expected optimal value for joint distributions consistent with the given multivariate marginals of the subsets in the partition. For univariate marginals, this bound was first proposed by Meilijson and Nadas (Journal … Read more

    Integer Solutions to Cutting Stock Problems

  • L. Fernández
  • C. Pola
    • Categories Applications - OR and Management Sciences Tags , ,

    We consider two integer linear programming models for the one-dimensional cutting stock problem that include various difficulties appearing in practical real problems. Our primary goals are the minimization of the trim loss or the minimization of the number of master rolls needed to satisfy the orders. In particular, we study an approach based on the … Read more

    Facets of the minimum-adjacency vertex coloring polytope

  • Diego Delle Donne
  • Javier Marenco
    • Categories 0-1 Programming, Polyhedra Tags , ,

    In this work we study a particular way of dealing with interference in combinatorial optimization models representing wireless communication networks. In a typical wireless network, co-channel interference occurs whenever two overlapping antennas use the same frequency channel, and a less critical interference is generated whenever two overlapping antennas use adjacent channels. This motivates the formulation … Read more

    Methods for Convex and General Quadratic Programming

  • Philip E. Gill
  • Elizabeth Wong
    • Categories Quadratic Programming Tags , , , , ,

    Computational methods are considered for finding a point that satisfies the second-order necessary conditions for a general (possibly nonconvex) quadratic program (QP). The first part of the paper considers the formulation and analysis of an active-set method for a generic QP with both equality and inequality constraints. The method uses a search direction that is … Read more

    Lower bounds for the Chvátal-Gomory rank in the 0/1 cube

  • Sebastian Pokutta
  • Gautier Stauffer
    • Categories 0-1 Programming, Cutting Plane Approaches

    Although well studied, important questions on the rank of the Chvátal-Gomory operator when restricting to polytopes contained in the n-dimensional 0/1 cube have not been answered yet. In particular, the question on the maximal rank of the Chvátal-Gomory procedure for this class of polytopes is still open. So far, the best-known upper bound is O(n^2 … Read more

    An Introduction to a Class of Matrix Cone Programming

  • Chao Ding
  • Defeng Sun
  • Kim-Chuan Toh
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , ,

    In this paper, we define a class of linear conic programming (which we call matrix cone programming or MCP) involving the epigraphs of five commonly used matrix norms and the well studied symmetric cone. MCP has recently found many important applications, for example, in nuclear norm relaxations of affine rank minimization problems. In order to … Read more

    Consistency of robust optimization

  • Ralf Werner
    • Categories Finance and Economics, Robust Optimization

    In recent years the robust counterpart approach, introduced and made popular by Ben-Tal, Nemirovski and El Ghaoui, gained more and more interest among both academics and practitioners. However, to the best of our knowledge, only very few results on the relationship between the original problem instance and the robust counterpart have been established. This exposition … Read more

    Burer’s Key Assumption for Semidefinite and Doubly Nonnegative Relaxations

  • Florian Jarre
    • Categories Approximation Algorithms, Quadratic Programming, Semi-definite Programming Tags , ,

    Burer has shown that completely positive relaxations of nonconvex quadratic programs with nonnegative and binary variables are exact when the binary variables satisfy a so-called key assumption. Here we show that introducing binary variables to obtain an equivalent problem that satisfies the key assumption will not improve the semidefinite relaxation, and only marginally improve the … Read more

    Templates for Convex Cone Problems with Applications to Sparse Signal Recovery

  • Stephen Becker
  • Emmanuel Candès
  • Michael Grant
    • Categories Constrained Nonlinear Optimization, Linear, Cone and Semidefinite Programming, Nonsmooth Optimization Tags , , , , , , ,

    This paper develops a general framework for solving a variety of convex cone problems that frequently arise in signal processing, machine learning, statistics, and other fi elds. The approach works as follows: first, determine a conic formulation of the problem; second, determine its dual; third, apply smoothing; and fourth, solve using an optimal first-order method. A … Read more

    The Split Variational Inequality Problem

  • Yair Censor
  • Aviv Gibali
  • Simeon Reich
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization Tags , , , ,

    We propose a new variational problem which we call the Split Variational Inequality Problem (SVIP). It entails finding a solution of one Variational Inequality Problem (VIP), the image of which under a given bounded linear transformation is a solution of another VIP. We construct iterative algorithms that solve such problems, under reasonable conditions, in Hilbert … Read more