Compact mixed-integer programming relaxations in quadratic optimization

  • Ben Beach
  • Robert Hildebrand
  • Joey Huchette
    • Categories (Mixed) Integer Nonlinear Programming, 0-1 Programming, Global Optimization

    We present a technique for producing valid dual bounds for nonconvex quadratic optimization problems. The approach leverages an elegant piecewise linear approximation for univariate quadratic functions due to Yarotsky, formulating this (simple) approximation using mixed-integer programming (MIP). Notably, the number of constraints, binary variables, and auxiliary continuous variables used in this formulation grows logarithmically in … Read more

    Contextual Chance-Constrained Programming

  • Hamed Rahimian
  • Bernardo K. Pagnoncelli
    • Categories Stochastic Programming Tags , , , ,

    Uncertainty in classical stochastic programming models is often described solely by independent random parameters, ignoring their dependence on multidimensional features. We describe a novel contextual chance-constrained programming formulation that incorporates features, and argue that solutions that do not take them into account may not be implementable. Our formulation cannot be solved exactly in most cases, … Read more

    Cost-Sharing Mechanism Design for Ride-Sharing

  • Maged M. Dessouky
  • Nelson A. Uhan
  • Shichun Hu
  • Phebe Vayanos
    • Categories Game Theory, Transportation

    In this paper, we focus on the cost-sharing problem for ride-sharing that determines how to allocate the total ride cost between the driver and the passengers. We identify the properties that a desirable cost-sharing mechanism should have and develop a general framework which can be used to create specific cost-sharing mechanisms. We propose specific mechanisms … Read more

    Decentralized Failure-Tolerant Optimization of Electric Vehicle Charging

  • Ignacio Aravena
  • Steve Chaping
  • Colin Ponce
    • Categories Convex Optimization, Energy, Scheduling Tags , , ,

    We present a decentralized failure-tolerant algorithm for optimizing electric vehicle (EV) charging, using charging stations as computing agents. The algorithm is based on the alternating direction method of multipliers (ADMM) and it has the following features: (i) It handles capacity, peak demand, and ancillary services coupling constraints. (ii) It does not require a central agent … Read more

    Amenable cones are particularly nice

  • Bruno F. Lourenço
  • Vera Roshchina
  • James Saunderson
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming

    Amenability is a geometric property of convex cones that is stronger than facial exposedness and assists in the study of error bounds for conic feasibility problems. In this paper we establish numerous properties of amenable cones, and investigate the relationships between amenability and other properties of convex cones, such as niceness and projectional exposure. We … Read more

    A Primal-Dual Algorithm for Risk Minimization

  • Drew P. Kouri
  • Thomas Surowiec
    • Categories Infinite Dimensional Optimization, Nonsmooth Optimization, Stochastic Programming Tags , , ,

    In this paper, we develop an algorithm to efficiently solve risk-averse optimization problems posed in reflexive Banach space. Such problems often arise in many practical applications as, e.g., optimization problems constrained by partial differential equations with uncertain inputs. Unfortunately, for many popular risk models including the coherent risk measures, the resulting risk-averse objective function is … Read more

    On Generating Lagrangian Cuts for Two-stage Stochastic Integer Programs

  • Rui Chen
  • James R. Luedtke
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , ,

    We investigate new methods for generating Lagrangian cuts to solve two-stage stochastic integer programs. Lagrangian cuts can be added to a Benders reformulation, and are derived from solving single scenario integer programming subproblems identical to those used in the nonanticipative Lagrangian dual of a stochastic integer program. While Lagrangian cuts have the potential to significantly … Read more

    Finding the Sequence of Largest Small n-Polygons by Numerical Optimization

  • Ignacio Castillo
  • Frank J. Kampas
  • János Pintér
    • Categories Applications - OR and Management Sciences, Nonlinear Optimization, Optimization Software and Modeling Systems

    LSP(n), the largest small polygon with n vertices, is the polygon of unit diameter that has maximal area A(n). It is known that for all odd values n≥3, LSP(n) is the regular n-polygon; however, this statement is not valid for even values of n. Finding the polygon LSP(n) and A(n) for even values n≥6 has … Read more

    A study of the relation between the single-row and the double-row facility layout problem

  • Mirko Dahlbeck
  • Anja Fischer
  • Philipp Hungerländer
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Facility Planning and Design Tags , ,

    The NP-hard Multi-Row Facility Layout Problem (MRFLP) consists of a set of one-dimensional departments and pairwise transport weights between them. It asks for a non-overlapping arrangement of the departments along a given number of rows such that the weighted sum of the horizontal center-to-center distances between the departments is minimized. We mainly focus on the … Read more

    A Geometric View of SDP Exactness in QCQPs and its Applications

  • Fatma Kılınç-Karzan
  • Alex L. Wang
    • Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming Tags , , ,

    Let S denote a subset of Rn defined by quadratic equality and inequality constraints and let S denote its projected semidefinite program (SDP) relaxation. For example, take S and S to be the epigraph of a quadratically constrained quadratic program (QCQP) and the projected epigraph of its SDP relaxation respectively. In this paper, we suggest … Read more