By Hanif D. Sherali

This publication offers with the idea and functions of the Reformulation- Linearization/Convexification approach (RL T) for fixing nonconvex optimization difficulties. A unified remedy of discrete and non-stop nonconvex programming difficulties is gifted utilizing this process. 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 . may 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 significant thrust is to start with a version that provides an invaluable illustration and constitution, after which to additional develop this illustration via computerized reformulation and constraint new release strategies. As pointed out above, the point of interest of this booklet is the improvement and alertness of RL T to be used as an automated reformulation strategy, and in addition, to generate powerful legitimate inequalities. The RLT operates in levels. within the Reformulation part, particular types of extra implied polynomial constraints, that come with the aforementioned constraints on the subject of binary variables, are appended to the matter. The ensuing challenge is consequently linearized, other than that sure convex constraints are often retained in XV specific specific situations, within the Linearization/Convexijication section. this is often performed through the definition of compatible new variables to interchange each one exact 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

Similar counting & numeration books

Sets, Logic and Maths for Computing

This easy-to-follow textbook introduces the mathematical language, wisdom and problem-solving talents that undergraduates have to research computing. The language is partly qualitative, with options corresponding to set, relation, functionality and recursion/induction; however it can also be partially quantitative, with rules of counting and finite chance.

Nuclear Computational Science: A Century in Review

Nuclear engineering has passed through broad growth through the years. long ago century, great advancements were made and with particular connection with the mathematical conception and computational technology underlying this self-discipline, advances in components reminiscent of high-order discretization tools, Krylov tools and generation Acceleration have gradually grown.

Analysis of Low-Speed Unsteady Airfoil Flows

This ebook presents an advent to unsteady aerodynamics with emphasis at the research and computation of inviscid and viscous two-dimensional flows over airfoils at low speeds. It starts off with a dialogue of the physics of unsteady flows and a proof of raise and thrust new release, airfoil flutter, gust reaction and dynamic stall.

Clifford Algebras: Geometric Modelling and Chain Geometries with Application in Kinematics

After revising identified representations of the crowd of Euclidean displacements Daniel Klawitter offers a entire creation into Clifford algebras. The Clifford algebra calculus is used to build new types that permit descriptions of the gang of projective changes and inversions with appreciate to hyperquadrics.

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

Example text

_ 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.

M. 4b) polynomial expressions Fd(J1,12 ) and ykFd(J1 ,12 ) under such a substitution, we obtain the following polyhedral set xd whose projection onto the (x, y) space is claimed to yield a relaxation for X: 28 Sherali and Adams xd = {(x,y,w, v): m I. rrkt; ut. 12) k=l ;::: o for r = 1, ... 5b) and for each (J1 , J 2 ) of order d}. 6) Xd} ford= 0,1, ... ,n. 7) where XPO =X 0 (for d = 0) denotes the ordinary linear programming relaxation, and conv(X) denotes the convex hull of X. J (or x. ) J J = 0) for each binary variable, this process would have simply produced a relaxation that is equivalent to the ordinary LP relaxation.

But first, let us introduce the following transformation which we shall find useful throughout this analysis. 2. ] (-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, ...

Download PDF sample

Download A Reformulation-Linearization Technique for Solving Discrete by Hanif D. Sherali PDF
Rated 4.55 of 5 – based on 45 votes