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

By Hanif D. Sherali

This publication offers with the idea and purposes of the Reformulation- Linearization/Convexification method (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 forms of nonconvexities is made through a polynomial illustration of discrete constraints. for instance, the binariness on a 0-1 variable x . will 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 critical thrust is to start with a version that presents an invaluable illustration and constitution, after which to extra enhance this illustration via automated reformulation and constraint new release innovations. As pointed out above, the point of interest of this booklet is the advance and alertness of RL T to be used as an automated reformulation method, 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 on the subject of binary variables, are appended to the matter. The ensuing challenge is consequently linearized, other than that definite convex constraints are often retained in XV specific distinctive situations, within the Linearization/Convexijication section. this can be performed through the definition of compatible new variables to interchange every one distinctive 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

Sparse Grid Quadrature in High Dimensions with Applications in Finance and Insurance

This publication offers with the numerical research and effective numerical therapy of high-dimensional integrals utilizing sparse grids and different dimension-wise integration thoughts with purposes to finance and assurance. The e-book specializes in offering insights into the interaction among coordinate changes, potent dimensions and the convergence behaviour of sparse grid tools.

Applied Laplace Transforms and z-Transforms for Scientists and Engineers: A Computational Approach using a Mathematica Package

The speculation of Laplace transformation is a crucial a part of the mathematical historical past required for engineers, physicists and mathematicians. Laplace transformation tools offer effortless and potent options for fixing many difficulties bobbing up in a variety of fields of technology and engineering, specifically for fixing differential equations.

Systems of Conservation Laws: Two-Dimensional Riemann Problems

This paintings should still function an introductory textual content for graduate scholars and researchers operating within the vital zone of partial differential equations with a spotlight on difficulties regarding conservation legislation. the single needful for the reader is a data of the simple thought of partial differential equations.

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

Sample text

Sherali and Myers (1989) also discuss and test various strategies and provide guidelines for composing suitable Lagrangian dual formulations. Second, an appropriate nondifferentiable optimization technique must be employed to solve the Lagrangian dual problem. Cutting plane or outer linearization methods (see Bazaraa and Goode, 1979) can quickly accumulate far too many constraints in the master program, and thereby get bogged down. The frrst-order subgradient methods of Poljak (1967, 1969), and Held et al.

On the other hand, a Lagrangian duality based scheme can not only exploit the inherent special structures, but can quickly provide near optimal primal and dual solutions that serve the purpose of obtaining tight lower and upper bounds. However, for a successful use of this technique, there are two critical issues. First, an appropriate formulation of the underlying Lagrangian dual must be constructed (see Shapiro, 1979, and Fisher, 1981). Sherali and Myers (1989) also discuss and test various strategies and provide guidelines for composing suitable Lagrangian dual formulations.

Let x be any binary vector. 23a) and A = nAx. w1 jeJ 1 for all k and vA Jk = 1, ... , 1 jeJ J ~:; N with I Jl = 1, ... , d. 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, ...

Download PDF sample

Rated 4.57 of 5 – based on 27 votes