By Hanif D. Sherali

ISBN-10: 1441948082

ISBN-13: 9781441948083

ISBN-10: 1475743882

ISBN-13: 9781475743883

This booklet offers with the speculation and functions of the Reformulation- Linearization/Convexification process (RL T) for fixing nonconvex optimization difficulties. A unified remedy of discrete and non-stop nonconvex programming difficulties is gifted utilizing this procedure. In essence, the bridge among those varieties of nonconvexities is made through a polynomial illustration of discrete constraints. for instance, the binariness on a 0-1 variable x . might be equivalently J expressed because the polynomial constraint x . (1-x . ) = zero. the inducement for this ebook is J J the function of tight linear/convex programming representations or relaxations in fixing such discrete and non-stop nonconvex programming difficulties. The relevant thrust is to begin with a version that presents an invaluable illustration and constitution, after which to extra boost this illustration via automated reformulation and constraint new release options. As pointed out above, the focus of this publication is the improvement and alertness of RL T to be used as an automated reformulation technique, and in addition, to generate robust legitimate inequalities. The RLT operates in levels. within the Reformulation section, specific sorts of extra implied polynomial constraints, that come with the aforementioned constraints in relation to binary variables, are appended to the matter. The ensuing challenge is accordingly linearized, other than that definite convex constraints are often retained in XV specific unique circumstances, within the Linearization/Convexijication part. this is often performed through the definition of compatible new variables to interchange every one special variable-product time period. the better dimensional illustration yields a linear (or convex) programming relaxation.

Show description

Read Online or Download A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems PDF

Similar counting & numeration books

Computational commutative algebra by Martin Kreuzer PDF

This publication is the usual continuation of Computational Commutative Algebra 1 with a few twists. the most a part of this e-book is a panoramic passeggiata throughout the computational domain names of graded earrings and modules and their Hilbert features. along with Gr? bner bases, we come upon Hilbert bases, border bases, SAGBI bases, or even SuperG bases.

New PDF release: Foreign-Exchange-Rate Forecasting with Artificial Neural

This ebook specializes in forecasting foreign currencies premiums through synthetic neural networks (ANNs), growing and utilising the hugely important computational suggestions of synthetic Neural Networks (ANNs) to foreign-exchange price forecasting. the result's an up to date assessment of the newest learn advancements in forecasting foreign currency echange charges coupled with a hugely invaluable methodological method of predicting fee adjustments in foreign currencies exchanges.

Download e-book for iPad: Computational Conformal Mapping by Prem Kythe

"There are greater than seventy five case stories of concrete conformal maps and greater than ninety five end-of-chapter workouts. .. available to graduate scholars. .. it may additionally function a instruction manual for scientists and engineers who are looking to paintings with conformal maps. .. The publication is a welcome boost to the literature. Its plentiful offer of case stories of conformal maps among given domain names and the end-of bankruptcy routines are quite beautiful and worthy.

Jochen Garcke, Dirk Pflüger's Sparse Grids and Applications - Stuttgart 2014 PDF

This quantity of LNCSE is a set of the papers from the complaints of the 3rd workshop on sparse grids and purposes. Sparse grids are a favored procedure for the numerical remedy of high-dimensional difficulties. the place classical numerical discretization schemes fail in additional than 3 or 4 dimensions, sparse grids, of their varied guises, are often the tactic of selection, be it spatially adaptive within the hierarchical foundation or through the dimensionally adaptive blend procedure.

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

Example text

2. 4, respectively. 5, one dealing with the treatment of equality constraints, and the other dealing with nonlinear, polynomial mixed-integer zero-one programming problems. As we shall see, the RLT process is equally applicable to this latter, more general, class of problems, and generates a similar hierarchy of nested polyhedral relaxations, leading to the convex hull of feasible solutions. 1. l)correspondingtoanylevel de {O,l, ... ,n}. Ford= 0, the relaxation X0 is simply the LP relaxation obtained by deleting the integrality restrictions on the xvariables.

D Equation (2. 7) has thus been established. A few remarks are pertinent at this point. 1. 7) to hold true, and that the foregoing analysis holds by simply eliminating any RLT product constraints that correspond to nonexistent bounding restrictions. 2 asserts that xis binary valued at an optimum to any linear program max{cx + dy: (x, y) E XPn} for which there exists an optimal solution, that is, for which this LP is not unbounded. 7) holds true in this case as well. 2. 7) is that the convex hull representation over subsets of the x-variables can be computed in an identical fashion.

4b), w 0 J J = 1, ... , n. Similarly, for each k = 1, ... ,;;;N. 4b), v 0 k =yk fork:::: l, ... ,m. = J L J~N:jeJ UJfor j = 1, ... ,n and yk = L J~N U~ fork= 1, ... ,m. Proof. 16) equals 0 whenever H :1:- 0, and equals 1 when H = 0. 13b) must be satisfied, yielding a unique solution. 13). 14b). 13b) for J = {j}, j = 1, ... , n, k = 1, ... , m, the proof is complete. 3. 14), for example. Then for any k e {1, ... 14) is as follows: - uk123' vl23k - _ uk VIk- v3k I+ -- uk3 + - uk12 vi2k - uk 12 + uk13 + uk 13 + uk23 + + uk123' uk vi3k = _ uk 123' V2k- uk123' uk13 + k uk123' k k 2 +UI2 +U23 +UI23' + uk123' 39 A Reformulation-Linearization Technique v0k - = yk = uk 0 + uk 1 + uk + 2 uk 3 uk + + 12 uk l3 + uk 23 + uk 123" The following theorem now provides the desired convex.

Download PDF sample

A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems by Hanif D. Sherali


by Joseph
4.0

Rated 4.36 of 5 – based on 24 votes