Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1035.90064
Tawarmalani, Mohit; Ahmed, Shabbir; Sahinidis, Nikolaos V.
Product disaggregation in global optimization and relaxations of rational programs. (English)
[J] Optim. Eng. 3, No. 3, 281-303 (2002). ISSN 1389-4420; ISSN 1573-2924/e

Summary: 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. \par 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 N\cal P$-hard. Finally, we present computational experience to demonstrate that product disaggregation is a useful reformulation technique for global optimization problems.

MSC 2000:: *90C26 Nonconvex programming
90C32 Fractional programming

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

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]