Month: March 2019

Doubly nonnegative relaxations are equivalent to completely positive reformulations of quadratic optimization problems with block-clique graph structures

  • Sunyoung Kim
  • Masakazu Kojima
  • Kim-Chuan Toh
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , , ,

    We study the equivalence among a nonconvex QOP, its CPP and DNN relaxations under the assumption that the aggregated and correlative sparsity of the data matrices of the CPP relaxation is represented by a block-clique graph $G$. By exploiting the correlative sparsity, we decompose the CPP relaxation problem into a clique-tree structured family of smaller … Read more

    Multi-Objective Optimization for Politically Fair Districting: A Scalable Multilevel Approach

  • Rahul Swamy
  • Douglas King
  • Sheldon Jacobson
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Multi-Criteria Optimization Tags , , , , , , ,

    Political districting in the United States is a decennial process of redrawing the boundaries of congressional and state legislative districts. The notion of fairness in political districting has been an important topic of subjective debate, with district maps having consequences to multiple stakeholders. Even though districting as an optimization problem has been well-studied, existing models … Read more

    Using two-dimensional Projections for Stronger Separation and Propagation of Bilinear Terms

  • Ambros Gleixner
  • Felipe Serrano
  • Benjamin Müller
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Nonlinear Optimization Tags , , , , , ,

    One of the most fundamental ingredients in mixed-integer nonlinear programming solvers is the well- known McCormick relaxation for a product of two variables x and y over a box-constrained domain. The starting point of this paper is the fact that the convex hull of the graph of xy can be much tighter when computed over … Read more

    On the depth of cutting planes

  • Laurent Poirrier
  • James Yu
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Cutting Plane Approaches Tags , ,

    We introduce a natural notion of depth that applies to individual cutting planes as well as entire families. This depth has nice properties that make it easy to work with theoretically, and we argue that it is a good proxy for the practical strength of cutting planes. In particular, we show that its value lies … Read more

    A Decomposition Heuristic for Mixed-Integer Supply Chain Problems

  • Lars Schewe
  • Martin Schmidt
  • Dieter Weninger
    • Categories (Mixed) Integer Linear Programming, Supply Chain Management Tags , , , ,

    Mixed-integer supply chain models typically are very large but are also very sparse and can be decomposed into loosely coupled blocks. In this paper, we use general-purpose techniques to obtain a block decomposition of supply chain instances and apply a tailored penalty alternating direction method, which exploits the structural properties of the decomposed instances. We … Read more

    Inertial Block Mirror Descent Method for Non-Convex Non-Smooth Optimization

  • Nicolas Gillis
  • Le Thi Khanh Hien
  • Panagiotis Patrinos
    • Categories Constrained Nonlinear Optimization Tags , , , , ,

    In this paper, we propose inertial versions of block coordinate descent methods for solving non-convex non-smooth composite optimization problems. We use the general framework of Bregman distance functions to compute the proximal maps. Our method not only allows using two different extrapolation points to evaluate gradients and adding the inertial force, but also takes advantage … Read more

    On Electricity Market Equilibria with Storage: Modeling, Uniqueness, and a Distributed ADMM

  • Julia Grübel
  • Thomas Kleinert
  • Vanessa Krebs
  • Lars Schewe
  • Martin Schmidt
  • Johannes Thürauf
  • Galina Orlinskaya
    • Categories Convex Optimization, Parallel Algorithms, Quadratic Programming Tags , , , , , ,

    We consider spot-market trading of electricity including storage operators as additional agents besides producers and consumers. Storages allow for shifting produced electricity from one time period to a later one. Due to this, multiple market equilibria may occur even if classical uniqueness assumptions for the case without storages are satisfied. For models containing storage operators, … Read more

    Computing Feasible Points of Bilevel Problems with a Penalty Alternating Direction Method

  • Thomas Kleinert
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , , ,

    Bilevel problems are highly challenging optimization problems that appear in many applications of energy market design, critical infrastructure defense, transportation, pricing, etc. Often, these bilevel models are equipped with integer decisions, which makes the problems even harder to solve. Typically, in such a setting in mathematical optimization one develops primal heuristics in order to obtain … Read more

    An Enhanced Logical Benders Approach for Linear Programs with Complementarity

  • Francisco Jara-Moroni
  • John E. Mitchell
  • Jong-Shi Pang
    • Categories Complementarity and Variational Inequalities, Global Optimization, Nonlinear Optimization Tags , ,

    This work extends the ones of Hu et al. (2008) and Bai et al. (2013) of a logical Benders approach for globally solving Linear Programs with Complementarity Constraints. By interpreting the logical Benders method as a reversed branch-and-bound method, where the whole exploration procedure starts from the leaf nodes in an enumeration tree, we provide … Read more

    A Robust Optimization Approach for the Unrelated Parallel Machine Scheduling Problem

  • Jonathan De La Vega
  • Reinaldo Morabito
  • Pedro Munari
  • Alfredo Moreno
    • Categories Applications - OR and Management Sciences, Scheduling

    In this paper, we address the Unrelated Parallel Machine Scheduling Problem (UPMSP) with sequence- and machine-dependent setup times and job due-date constraints. Different uncertainties are typically involved in real-world production planning and scheduling problems. If ignored, they can lead to suboptimal or even infeasible schedules. To avoid this, we present two new robust optimization models … Read more