Skip to main content
SpringerLink
Log in
Book cover

A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems

  • Book
  • © 1999

Overview

Authors:
  1. Hanif D. Sherali

    1. Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, Blacksburg, USA

    View author publications

    You can also search for this author in PubMed   Google Scholar

  2. Warren P. Adams

    1. Department of Mathematical Sciences, Clemson University, Clemson, USA

    View author publications

    You can also search for this author in PubMed   Google Scholar

Part of the book series: Nonconvex Optimization and Its Applications (NOIA, volume 31)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 169.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 219.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book USD 219.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (11 chapters)

  1. Front Matter

    Pages i-xxiii
    Download chapter PDF

  2. Introduction

    1. Introduction

      • Hanif D. Sherali, Warren P. Adams
      Pages 1-20

  3. Discrete Nonconvex Programs

    1. Front Matter

      Pages 21-21
      Download chapter PDF

    2. RLT Hierarchy for Mixed-Integer Zero-One Problems

      • Hanif D. Sherali, Warren P. Adams
      Pages 23-60

    3. Generalized Hierarchy for Exploiting Special Structures in Mixed-Integer Zero-One Problems

      • Hanif D. Sherali, Warren P. Adams
      Pages 61-102

    4. RLT Hierarchy for General Discrete Mixed-Integer Problems

      • Hanif D. Sherali, Warren P. Adams
      Pages 103-129

    5. Generating Valid Inequalities and Facets Using RLT

      • Hanif D. Sherali, Warren P. Adams
      Pages 131-183

    6. Persistency in Discrete Optimization

      • Hanif D. Sherali, Warren P. Adams
      Pages 185-260

  4. Continuous Nonconvex Programs

    1. Front Matter

      Pages 261-261
      Download chapter PDF

    2. RLT-Based Global Optimization Algorithms for Nonconvex Polynomial Programming Problems

      • Hanif D. Sherali, Warren P. Adams
      Pages 263-295

    3. Reformulation-Convexification Technique for Quadratic Programs and Some Convex Envelope Characterizations

      • Hanif D. Sherali, Warren P. Adams
      Pages 297-367

    4. Reformulation-Convexification Technique for Polynomial Programs: Design and Implementation

      • Hanif D. Sherali, Warren P. Adams
      Pages 369-402

  5. Special Applications to Discrete and Continuous Nonconvex Programs

    1. Front Matter

      Pages 403-403
      Download chapter PDF

    2. Applications to Discrete Problems

      • Hanif D. Sherali, Warren P. Adams
      Pages 405-439

    3. Applications to Continuous Problems

      • Hanif D. Sherali, Warren P. Adams
      Pages 441-491

  6. Back Matter

    Pages 493-516
    Download chapter PDF
Back to top

Keywords

About this book

This book deals with the theory and applications of the Reformulation- Linearization/Convexification Technique (RL T) for solving nonconvex optimization problems. A unified treatment of discrete and continuous nonconvex programming problems is presented using this approach. In essence, the bridge between these two types of nonconvexities is made via a polynomial representation of discrete constraints. For example, the binariness on a 0-1 variable x . can be equivalently J expressed as the polynomial constraint x . (1-x . ) = 0. The motivation for this book is J J the role of tight linear/convex programming representations or relaxations in solving such discrete and continuous nonconvex programming problems. The principal thrust is to commence with a model that affords a useful representation and structure, and then to further strengthen this representation through automatic reformulation and constraint generation techniques. As mentioned above, the focal point of this book is the development and application of RL T for use as an automatic reformulation procedure, and also, to generate strong valid inequalities. The RLT operates in two phases. In the Reformulation Phase, certain types of additional implied polynomial constraints, that include the aforementioned constraints in the case of binary variables, are appended to the problem. The resulting problem is subsequently linearized, except that certain convex constraints are sometimes retained in XV particular special cases, in the Linearization/Convexijication Phase. This is done via the definition of suitable new variables to replace each distinct variable-product term. The higher dimensional representation yields a linear (or convex) programming relaxation.

Authors and Affiliations

  • Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, Blacksburg, USA

    Hanif D. Sherali

  • Department of Mathematical Sciences, Clemson University, Clemson, USA

    Warren P. Adams

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation