reformulation-linearization technique

Polyhedral Properties of RLT Relaxations of Nonconvex Quadratic Programs and Their Implications on Exact Relaxations

  • Yuzhou Qiu
  • E. Alper Yildirim
    • Categories Global Optimization, Linear Programming, Quadratic Programming Tags , , ,

    We study linear programming relaxations of nonconvex quadratic programs given by the reformulation-linearization technique (RLT), referred to as RLT relaxations. We investigate the relations between the polyhedral properties of the feasible regions of a quadratic program and its RLT relaxation. We establish various connections between recession directions, boundedness, and vertices of the two feasible regions. … Read more

    On Exact and Inexact RLT and SDP-RLT Relaxations of Quadratic Programs with Box Constraints

  • Yuzhou Qiu
  • E. Alper Yildirim
    • Categories Bound-constrained Optimization, Global Optimization, Quadratic Programming Tags , , ,

    Quadratic programs with box constraints involve minimizing a possibly nonconvex quadratic function subject to lower and upper bounds on each variable. This is a well-known NP-hard problem that frequently arises in various applications. We focus on two convex relaxations, namely the RLT (Reformulation-Linearization Technique) relaxation and the SDP-RLT relaxation obtained by adding semidefinite constraints to … Read more

    An extension of the Reformulation-Linearization Technique to nonlinear optimization

  • Danique de Moor
  • Dick den Hertog
  • Jianzhe Zhen
    • Categories Constrained Nonlinear Optimization, Global Optimization Tags , , ,

    We introduce a novel Reformulation-Perspectification Technique (RPT) to obtain convex approximations of nonconvex continuous optimization problems. RPT consists of two steps, those are, a reformulation step and a perspectification step. The reformulation step generates redundant nonconvex constraints from pairwise multiplication of the existing constraints. The perspectification step then convexifies the nonconvex components by using perspective … Read more

    Polyhedral Analysis of Symmetric Multilinear Polynomials over Box Constraints

  • Warren Adams
  • Akshay Gupte
  • Yibo Xu
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Polyhedra Tags , , , ,

    It is well-known that the convex and concave envelope of a multilinear polynomial over a box are polyhedral functions. Exponential-sized extended and projected formulations for these envelopes are also known. We consider the convexification question for multilinear polynomials that are symmetric with respect to permutations of variables. Such a permutation-invariant structure naturally implies a quadratic-sized … Read more

    A Reformulation-Linearization Technique for Optimization over Simplices

  • Dick den Hertog
  • Aras Selvi
  • Wolfram Wiesemann
    • Categories Constrained Nonlinear Optimization, Global Optimization, Global Optimization Theory Tags , ,

    We study non-convex optimization problems over simplices. We show that for a large class of objective functions, the convex approximation obtained from the Reformulation-Linearization Technique (RLT) admits optimal solutions that exhibit a sparsity pattern. This characteristic of the optimal solutions allows us to conclude that (i) a linear matrix inequality constraint, which is often added … Read more

    A Primal-Dual Perspective on Adaptive Robust Linear Optimization

  • Frans J.C.T. de Ruiter
  • Jianzhe Zhen
    • Categories Robust Optimization Tags , ,

    Adaptive robust optimization is a modelling paradigm for multistage optimization under uncertainty where one seeks decisions that minimize the worst-case cost with respect to all possible scenarios in a prescribed uncertainty set. However, optimal policies for adaptive robust optimization problems are difficult to compute. Therefore, one often restricts to the class of affine policies which … Read more

    Disjoint Bilinear Optimization: A Two-Stage Robust Optimization Perspective

  • Danique de Moor
  • Dick den Hertog
  • Ahmadreza Marandi
  • Lieven Vandenberghe
  • Jianzhe Zhen
    • Categories Robust Optimization Tags , , ,

    In this paper, we focus on a subclass of quadratic optimization problems, that is, disjoint bilinear optimization problems. We first show that disjoint bilinear optimization problems can be cast as two-stage robust linear optimization problems with fixed-recourse and right-hand-side uncertainty, which enables us to apply robust optimization techniques to solve the resulting problems. To this … Read more

    Lower Bounds for the Quadratic Minimum Spanning Tree Problem Based on Reduced Cost Computation

  • Federico Malucelli
  • Borzou Rostami
    • Categories Combinatorial Optimization, Quadratic Programming Tags , , , , ,

    The Minimum Spanning Tree Problem (MSTP) is one of the most known combinatorial optimization problems. It concerns the determination of a minimum edge-cost subgraph spanning all the vertices of a given connected graph. The Quadratic Minimum Spanning Tree Problem (QMSTP) is a variant of the MST whose cost considers also the interaction between every pair … Read more

    A Tight Lower Bound for the Adjacent Quadratic Assignment Problem

  • Pietro Belotti
  • Federico Malucelli
  • Borzou Rostami
    • Categories 0-1 Programming, Combinatorial Optimization Tags , , ,

    In this paper we address the Adjacent Quadratic Assignment Problem (AQAP) which is a variant of the QAP where the cost coefficient matrix has a particular structure. Motivated by strong lower bounds obtained by applying Reformulation Linearization Technique (RLT) to the classical QAP, we propose two special RLT representations for the problem. The first is … Read more

    Symmetry in RLT cuts for the quadratic assignment and standard quadratic optimization problems

  • Etienne de Klerk
  • Marianna Eisenberg-Nagy
  • Renata Sotirov
  • Uwe Truetsch
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    The reformulation-linearization technique (RLT), introduced in [W.P. Adams, H.D. Sherali, A tight linearization and an algorithm for zero-one quadratic programming problems, Management Science, 32(10):1274–1290, 1986], provides a way to compute linear programming bounds on the optimal values of NP-hard combinatorial optimization problems. In this paper we show that, in the presence of suitable algebraic symmetry … Read more