Branch-and-Sandwich: A Deterministic Global Optimization Algorithm for Optimistic Bilevel Programming Problems

  • Claire S. Adjiman
  • Polyxeni-Margarita Kleniati
    • Categories Global Optimization Theory Tags , ,

    We present a global optimization algorithm, Branch-and-Sandwich, for optimistic bilevel programming problems which satisfy a regularity condition in the inner problem. The functions involved are assumed to be nonconvex and twice continuously differentiable. The proposed approach can be interpreted as the exploration of two solution spaces (corresponding to the inner and the outer problems) using … Read more

    Efficient Heuristic Algorithms for Maximum Utility Product Pricing Problems

  • Tor G.J. Myklebust
  • M. A. Sharpe
  • Levent Tunçel
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Combinatorial Optimization Tags , , ,

    We propose improvements to some of the best heuristic algorithms for optimal product pricing problem originally designed by Dobson and Kalish in the late 1980’s and in the early 1990’s. Our improvements are based on a detailed study of a fundamental decoupling structure of the underlying mixed integer programming (MIP) problem and on incorporating more … Read more

    Two methods of pruning Benders’ cuts and their application to the management of a gas portfolio

  • Romain Apparigliato
  • Laurent Pfeiffer
  • Sophie Auchapt
    • Categories Finance and Economics, Stochastic Programming Tags , , , ,

    In this article, we describe a gas portfolio management problem, which is solved with the SDDP (Stochastic Dual Dynamic Programming) algorithm. We present some improvements of this algorithm and focus on methods of pruning Benders’ cuts, that is to say, methods of picking out the most relevant cuts among those which have been computed. Our … Read more

    The Generalized Trust Region Subproblem

  • Ting Kei Pong
  • Henry Wolkowicz
    • Categories Optimization Software and Modeling Systems, Unconstrained Optimization

    The \emph{interval bounded generalized trust region subproblem} (GTRS) consists in minimizing a general quadratic objective, $q_0(x) \rightarrow \min$, subject to an upper and lower bounded general quadratic constraint, $\ell \leq q_1(x) \leq u$. This means that there are no definiteness assumptions on either quadratic function. We first study characterizations of optimality for this \emph{implicitly} convex … Read more

    An extended approach for lifting clique tree inequalities

  • Anja Fischer
  • Frank Fischer
    • Categories Combinatorial Optimization, Polyhedra Tags , ,

    We present a new lifting approach for strengthening arbitrary clique tree inequalities that are known to be facet defining for the symmetric traveling salesman problem in order to get stronger valid inequalities for the symmetric quadratic traveling salesman problem (SQTSP). Applying this new approach to the subtour elimination constraints (SEC) leads to two new classes … Read more

    Clarke subgradients for directionally Lipschitzian stratifiable functions

  • Dmitriy Drusvyatskiy
  • Adrian Lewis
  • Alexander D. Ioffe
    • Categories Nonsmooth Optimization

    Using a geometric argument, we show that under a reasonable continuity condition, the Clarke subdifferential of a semi-algebraic (or more generally stratifiable) directionally Lipschitzian function admits a simple form: the normal cone to the domain and limits of gradients generate the entire Clarke subdifferential. The characterization formula we obtain unifies various apparently disparate results that … Read more

    Variational Properties of Value Functions

  • Aleksandr Y. Aravkin
  • James V. Burke
  • Michael P. Friedlander
    • Categories Convex and Nonsmooth Optimization Tags , ,

    Regularization plays a key role in a variety of optimization formulations of inverse problems. A recurring question in regularization approaches is the selection of regularization parameters, and its effect on the solution and on the optimal value of the optimization problem. The sensitivity of the value function to the regularization parameter can be linked directly … Read more

    Kullback-Leibler Divergence Constrained Distributionally Robust Optimization

  • Jeff L Hong
  • Zhaolin Hu
    • Categories Nonlinear Optimization, Robust Optimization, Stochastic Programming

    In this paper we study distributionally robust optimization (DRO) problems where the ambiguity set of the probability distribution is defined by the Kullback-Leibler (KL) divergence. We consider DRO problems where the ambiguity is in the objective function, which takes a form of an expectation, and show that the resulted minimax DRO problems can be formulated … Read more

    On the Relative Strength of Different Generalizations of Split Cuts

  • Sanjeeb Dash
  • Oktay Gunluk
  • Marco Molinaro
    • Categories Cutting Plane Approaches Tags , ,

    Split cuts are among the most important and well-understood cuts for general mixed-integer programs. In this paper we consider some recent generalizations of split cuts and compare their relative strength. More precisely, we compare the elementary closures of {split}, {cross}, {crooked cross} and general {multi-branch split cuts} as well as cuts obtained from multi-row and … Read more

    The Slater condition is generic in linear conic programming

  • Mirjam Dür
  • Georg Still
  • Bolor Jargalsaikhan
    • Categories Linear, Cone and Semidefinite Programming, Semi-infinite Programming

    We call a property generic if it holds for almost all problem instances. For linear conic problems, it has been shown in the literature that properties like uniqueness, strict complementarity or nondegeneracy of the optimal solution are generic under the assumption that Slater’s condition is fulfilled. The possibility that Slater’s condition generically fails has not … Read more