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

By Hanif D. Sherali

This ebook bargains with the idea and purposes of the Reformulation- Linearization/Convexification procedure (RL T) for fixing nonconvex optimization difficulties. A unified therapy of discrete and non-stop nonconvex programming difficulties is gifted utilizing this strategy. 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 . might be equivalently J expressed because the polynomial constraint x . (1-x . ) = zero. the incentive for this publication 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 start with a version that provides an invaluable illustration and constitution, after which to extra improve this illustration via automated reformulation and constraint iteration suggestions. As pointed out above, the point of interest of this e-book is the advance and alertness of RL T to be used as an automated reformulation strategy, and likewise, to generate robust 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 hence linearized, other than that convinced convex constraints are often retained in XV specific unique circumstances, within the Linearization/Convexijication part. this can be performed through the definition of compatible new variables to exchange every 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

Conservation Laws

Conservation legislation. Physics textbook. includes bankruptcy 1 - Conservation of strength, bankruptcy 2 - Simplifying the power Zoo, bankruptcy three - paintings: The move of Mechanical power, bankruptcy four - Conservation of Momentum, bankruptcy five - Conservation of Angular Momentum, suggestions to chose difficulties, and word list.

Modeling of physiological flows

"This publication bargains a mathematical replace of the state-of-the-art of the study within the box of mathematical and numerical types of the circulatory method. it truly is dependent into assorted chapters, written via amazing specialists within the box. Many primary matters are thought of, corresponding to: the mathematical illustration of vascular geometries extracted from scientific pictures, modelling blood rheology and the advanced multilayer constitution of the vascular tissue, and its attainable pathologies, the mechanical and chemical interplay among blood and vascular partitions, and different scales coupling neighborhood and systemic dynamics.

Stochastic Calculus: Applications in Science and Engineering

This paintings makes a speciality of examining and providing options for quite a lot of stochastic difficulties which are encountered in utilized arithmetic, chance, physics, engineering, finance, and economics. The process used reduces the space among the mathematical and engineering literature. Stochastic difficulties are outlined by way of algebraic, differential or necessary equations with random coefficients and/or enter.

Exercises in Computational Mathematics with MATLAB

Designed to supply instruments for autonomous learn, this ebook includes student-tested mathematical workouts joined with MATLAB programming workouts. so much chapters open with a evaluation by means of theoretical and programming workouts, with exact strategies supplied for all difficulties together with courses.

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

Example text

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

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, (11 ,12 ) k of order (d+1) imply that fd(J1,J2 ) ~ am f;(J 1,J2 ) ~ 0 for all = 1, ... , m, and (11, 12 ) of order d. Proof. Consider any (11 , 12 ) of order d with 0 S: d < nand any k e {1, ... , m}, and let t e N- (11 u J2 ). 11) f~+I(JI + t, 12) + f~+l(11, 12 + t) = f~(JI, 12). 11 ), and the proof is complete. D The equivalence of X to Xd for any d E { 0, ... , n} under integrality restrictions on the x-variables, and the hierarchy among the relaxations are established next. 1. 6), ford = 0, 1, ...

Download PDF sample

Rated 4.34 of 5 – based on 24 votes