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

By Hanif D. Sherali

This ebook offers with the speculation and functions 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 method. 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 primary thrust is to start with a version that offers an invaluable illustration and constitution, after which to extra enhance this illustration via automated reformulation and constraint new release thoughts. As pointed out above, the point of interest of this publication is the advance and alertness of RL T to be used as an automated reformulation technique, and likewise, to generate robust legitimate inequalities. The RLT operates in levels. within the Reformulation part, specific sorts of extra implied polynomial constraints, that come with the aforementioned constraints when it comes 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 targeted circumstances, within the Linearization/Convexijication section. this can be performed through the definition of compatible new variables to interchange each one targeted 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

Meshfree Particle Methods

Meshfree Particle equipment is a finished and systematic exposition of particle tools, meshfree Galerkin and partitition of solidarity tools, molecular dynamics equipment, and multiscale equipment. so much theories, computational formulations, and simulation effects provided are contemporary advancements in meshfree equipment.

Regularization of Inverse Problems (Mathematics and Its Applications)

Regularization of Inverse difficulties is my favourite a part of learn. .. In civileng. .that is uncommon so i'm going to recommand this booklet for civil engineer in my contry. .good ebook thank.

100 Volumes of ‘Notes on Numerical Fluid Mechanics’: 40 Years of Numerical Fluid Mechanics and Aerodynamics in Retrospect

This quantity includes 37 invited contributions, accrued to rejoice 100 volumes of the NNFM sequence. After a common creation overviews are given in 5 components of the advancements in numerical fluid mechanics and similar fields. within the first half information regarding the sequence is given, its origins are mentioned, in addition to its atmosphere and the German and ecu high-performance laptop scene.

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

Sample text

23b) 44 Sherali and Adams Proof. ~(11 ,12 ) match those of Fd(J1 ,12 ) and ykF/11 ,12 ), respectively, and so (X, y, w, v) E zd with X binary. Conversely, let (x, y, w, v) E Zd. 23) holds true. Note that for d = 1, the set Z1 has constraints x. ) 1 ~ (yk - v 'k) 1 ~ 0 for j = 1, ... , n, k = 1, ... , m. Hence, 0::;; yk ::;; 1, and for any j = 1, ... , n, if x1 = 0, then vJk = 0 = Yij' for k = l, ... ,m, while if x 1 = 1, then vJk = yk = ykxJ fork= l, ... ,m. , j = 1, ... 23) holds true. Therefore, the result is true for Z1 .

And relaxing integrality, the nonlinear polynomial problem is re-linearized J into a higher dimensional polyhedral set Xd defmed in terms of the original variables Sherali and Adams 10 (x, y) and the new variables (w, v). For Xd to be equivalent to X, it is only necessary to enforce x to be binary valued, with the remaining variables treated as continuous valued, since the binariness on the x-variables is shown to automatically enforce the required product relationships on the w- and v-variables.

Ym ). Given a value of d set E of bounded continuous variables {1, ... , n}, this RLT procedure constructs various polynomial factors of degree d comprised of the product of some d binary variables x j or their complements (1 - x j). These factors are then used to multiply each of the constraints defining X (including the variable bounding restrictions), to create a (nonlinear) polynomial mixed-integer zero-one programming problem. relationship x 2 J = x J. , j J = 1, ... , and relaxing integrality, the nonlinear polynomial problem is re-linearized J into a higher dimensional polyhedral set Xd defmed in terms of the original variables Sherali and Adams 10 (x, y) and the new variables (w, v).

Download PDF sample

Rated 4.94 of 5 – based on 23 votes