Download A Reformulation-Linearization Technique for Solving Discrete by Hanif D. Sherali PDF

By Hanif D. Sherali

This booklet offers with the idea and purposes of the Reformulation- Linearization/Convexification strategy (RL T) for fixing nonconvex optimization difficulties. A unified therapy of discrete and non-stop nonconvex programming difficulties is gifted utilizing this process. In essence, the bridge among those different types of nonconvexities is made through a polynomial illustration of discrete constraints. for instance, the binariness on a 0-1 variable x . may be equivalently J expressed because the polynomial constraint x . (1-x . ) = zero. the inducement for this booklet is J J the function of tight linear/convex programming representations or relaxations in fixing such discrete and non-stop nonconvex programming difficulties. The significant thrust is to begin with a version that offers an invaluable illustration and constitution, after which to additional enhance this illustration via automated reformulation and constraint iteration recommendations. As pointed out above, the focus of this e-book is the improvement and alertness of RL T to be used as an automated reformulation technique, and in addition, to generate powerful legitimate inequalities. The RLT operates in stages. within the Reformulation section, particular types of extra implied polynomial constraints, that come with the aforementioned constraints relating to binary variables, are appended to the matter. The ensuing challenge is thus linearized, other than that convinced convex constraints are often retained in XV specific distinctive instances, within the Linearization/Convexijication section. this can be performed through the definition of appropriate new variables to exchange each one specified variable-product time period. the better dimensional illustration yields a linear (or convex) programming relaxation.

Show description

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

Best counting & numeration books

Computational Commutative Algebra 2

This e-book is the typical continuation of Computational Commutative Algebra 1 with a few twists. the most a part of this e-book is a wide ranging passeggiata in the course of the computational domain names of graded earrings and modules and their Hilbert capabilities. along with Gr? bner bases, we come across Hilbert bases, border bases, SAGBI bases, or even SuperG bases.

Progress in industrial mathematics at ECMI 2006

Court cases from the 14th eu convention for arithmetic in held in Madrid current cutting edge numerical and mathematical innovations. themes contain the most recent functions in aerospace, info and communications, fabrics, power and surroundings, imaging, biology and biotechnology, lifestyles sciences, and finance.

Monte Carlo Strategies in Scientific Computing

This paperback version is a reprint of the 2001 Springer version. This e-book presents a self-contained and updated remedy of the Monte Carlo strategy and develops a typical framework below which a number of Monte Carlo strategies may be "standardized" and in comparison. Given the interdisciplinary nature of the subjects and a average prerequisite for the reader, this publication may be of curiosity to a wide viewers of quantitative researchers resembling computational biologists, computing device scientists, econometricians, engineers, probabilists, and statisticians.

Sparse Grids and Applications - Stuttgart 2014

This quantity of LNCSE is a suite of the papers from the lawsuits of the 3rd workshop on sparse grids and functions. Sparse grids are a well-liked strategy 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 various guises, are usually the tactic of selection, be it spatially adaptive within the hierarchical foundation or through the dimensionally adaptive blend procedure.

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

Sample text

1}'l''w JuJ , foralll~N. _ UJ0 WJ = J'~J J for J ~ N. ,;;; =1, and w. =x. 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.

In connection with the final comment above, we remark that Boros et al. (1989) have independently developed a similar hierarchy for the special case of the unconstrained, quadratic pseudo-Boolean programming problem. For this case, they construct a standard linear programming relaxation that coincides with our relaxation at level d = 1 , and then show in an existential fashion how a hierarchy of relaxations indexed by d = 1, ... , n leading up to the convex hull representation at level n can be generated.

Problems of this type have the following form, involving the optimization of a polynomial objective function subject to polynomial constraints in a set of continuous, bounded variables. Minimize {

Download PDF sample

Rated 4.57 of 5 – based on 30 votes