Month: August 2018

On Solving Two-Stage Distributionally Robust Disjunctive Programs with a General Ambiguity Set

  • Manish Bansal
  • Sanjay Mehrotra
    • Categories 0-1 Programming, Stochastic Programming

    We introduce two-stage distributionally robust disjunctive programs (TSDR-DPs) with disjunctive constraints in both stages and a general ambiguity set for the probability distributions. The TSDR-DPs subsume various classes of two-stage distributionally robust programs where the second stage problems are non-convex programs (such as mixed binary programs, semi-continuous program, nonconvex quadratic programs, separable non-linear programs, etc.). … Read more

    On the NP-hardness of deciding emptiness of the split closure of a rational polytope in the 0,1 hypercube

  • Dabeen Lee
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Cutting Plane Approaches Tags , ,

    Split cuts are prominent general-purpose cutting planes in integer programming. The split closure of a rational polyhedron is what is obtained after intersecting the half-spaces defined by all the split cuts for the polyhedron. In this paper, we prove that deciding whether the split closure of a rational polytope is empty is NP-hard, even when … Read more

    On the Rational Polytopes with Chvatal Rank 1

  • Gérard Cornuéjols
  • Dabeen Lee
  • Yanjun Li
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    We study the following problem: given a rational polytope with Chvatal rank 1, does it contain an integer point? Boyd and Pulleyblank observed that this problem is in the complexity class NP ∩ co-NP, an indication that it is probably not NP-complete. It is open whether there is a polynomial time algorithm to solve the … Read more

    On Some Polytopes Contained in the 0,1 Hypercube that Have a Small Chvatal Rank

  • Gérard Cornuéjols
  • Dabeen Lee
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Cutting Plane Approaches Tags , ,

    In this paper, we consider polytopes P that are contained in the unit hypercube. We provide conditions on the set of 0,1 vectors not contained in P that guarantee that P has a small Chvatal rank. Our conditions are in terms of the subgraph induced by these infeasible 0,1 vertices in the skeleton graph of … Read more

    A new dual for quadratic programming and its applications

  • Moslem Zamani
    • Categories Global Optimization Tags , , , ,

    The main outcomes of the paper are divided into two parts. First, we present a new dual for quadratic programs, in which, the dual variables are affine functions, and we prove strong duality. Since the new dual is intractable, we consider a modified version by restricting the feasible set. This leads to a new bound … Read more

    The Distributionally Robust Chance Constrained Vehicle Routing Problem

  • Shubhechyya Ghosal
  • Wolfram Wiesemann
    • Categories Robust Optimization, Stochastic Programming, Transportation Tags , ,

    We study a variant of the capacitated vehicle routing problem (CVRP), which asks for the cost-optimal delivery of a single product to geographically dispersed customers through a fleet of capacity-constrained vehicles. Contrary to the classical CVRP, which assumes that the customer demands are deterministic, we model the demands as a random vector whose distribution is … Read more

    Markov inequalities, Dubiner distance, norming meshes and polynomial optimization on convex bodies

  • Federico Piazzon
  • Marco Vianello
    • Categories Global Optimization Tags , , , , ,

    We construct norming meshes for polynomial optimization by the classical Markov inequality on general convex bodies in R^d, and by a tangential Markov inequality via an estimate of Dubiner distance on smooth convex bodies. These allow to compute a (1−eps)-approximation to the minimum of any polynomial of degree not exceeding n by O((n/sqrt(eps))^(ad)) samples, with … Read more

    The Value of Multi-stage Stochastic Programming in Risk-averse Unit Commitment under Uncertainty

  • Shabbir Ahmed
  • M. Selim Akturk
  • Özlem Cavus
  • Ali Irfan Mahmutogullari
    • Categories Stochastic Programming Tags , ,

    Day-ahead scheduling of electricity generation or unit commitment is an important and challenging optimization problem in power systems. Variability in net load arising from the increasing penetration of renewable technologies have motivated study of various classes of stochastic unit commitment models. In two-stage models, the generation schedule for the entire day is fixed while the … Read more

    Inexact Variable Metric Stochastic Block-Coordinate Descent for Regularized Optimization

  • Stephen Wright
  • Ching-pei Lee
    • Categories Convex Optimization, Nonsmooth Optimization

    Block-coordinate descent (BCD) is a popular framework for large-scale regularized optimization problems with block-separable structure. Existing methods have several limitations. They often assume that subproblems can be solved exactly at each iteration, which in practical terms usually restricts the quadratic term in the subproblem to be diagonal, thus losing most of the benefits of higher-order … Read more