Product Disaggregation in Global Optimization and Relaxations of Rational Programs

Authors: Tawarmalani M.1; Ahmed S.2; Sahinidis N.V.3

Source: Optimization and Engineering, Volume 3, Number 3, September 2002 , pp. 281-303(23)

Publisher: Springer

Key:
Free Content - Free Content
New Content - New Content
Subscribed Content - Subscribed Content
Free Trial Content - Free Trial Content

Abstract:

We consider the product of a single continuous variable and the sum of a number of continuous variables. We show that “product disaggregation” (distributing the product over the sum) leads to tighter linear programming relaxations, much like variable disaggregation does in mixed-integer linear programming. We also derive closed-form expressions characterizing the exact region over which these relaxations improve when the bounds of participating variables are reduced.

In a concrete application of product disaggregation, we develop and analyze linear programming relaxations of rational programs. In the process of doing so, we prove that the task of bounding general linear fractional functions of 0–1 variables is {\cal NP}-hard. Finally, we present computational experience to demonstrate that product disaggregation is a useful reformulation technique for global optimization problems.

Keywords: global optimization; relaxation gap; convex extensions; range reduction

Language: English

Document Type: Research article

Affiliations: 1: Krannert School of Management, Purdue University, West Lafayette, IN 47907-1310. mtawarma@mgmt.purdue.edu 2: School of Industrial and Systems Engineering, Georgia Institute of Technology, 765 Ferst Drive, Atlanta, GA 30332. sahmed@isye.gatech.edu 3: Department of Chemical and Biomolecular Engineering, University of Illinois at Urbana-Champaign, 600 South Mathews Avenue, Urbana, IL 61801. nikos@uiuc.edu

The full text electronic article is available for purchase. You will be able to download the full text electronic article after payment.

$47.00 plus tax      Refund Policy

 

OR

Back to top

Key:
Free Content - Free Content
New Content - New Content
Subscribed Content - Subscribed Content
Free Trial Content - Free Trial Content
Share this item with others: These icons link to social bookmarking sites where readers can share and discover new web pages.
Page Help Click here for Page Help
Shopping cart
Tools
Sign in






Need to register?
Sign up here
Text size: A | A | A | A