Download e-book for kindle: A Reformulation-Linearization Technique for Solving Discrete by Hanif D. Sherali

By Hanif D. Sherali

ISBN-10: 1441948082

ISBN-13: 9781441948083

ISBN-10: 1475743882

ISBN-13: 9781475743883

This ebook offers with the idea and purposes of the Reformulation- Linearization/Convexification procedure (RL T) for fixing nonconvex optimization difficulties. A unified remedy of discrete and non-stop nonconvex programming difficulties is gifted utilizing this procedure. 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 . should 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 important thrust is to begin with a version that provides an invaluable illustration and constitution, after which to extra improve this illustration via computerized reformulation and constraint new release thoughts. 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 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 as a consequence linearized, other than that sure convex constraints are often retained in XV specific detailed situations, within the Linearization/Convexijication section. this can be performed through the definition of appropriate new variables to exchange each one special 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

Read e-book online Upscaling multiphase flow in porous media: from pore to core PDF

This ebook offers concise, updated and easy-to-follow info on definite features of an ever very important study region: multiphase movement in porous media. This movement kind is of serious value in lots of petroleum and environmental engineering difficulties, equivalent to in secondary and tertiary oil restoration, subsurface remediation and CO2 sequestration.

Simon Sirca, Martin Horvat's Computational Methods for Physicists: Compendium for PDF

This e-book is helping complicated undergraduate, graduate and postdoctoral scholars of their day-by-day paintings by means of providing them a compendium of numerical tools. the alternative of equipment can pay major cognizance to mistakes estimates, balance and convergence concerns in addition to to the how one can optimize application execution speeds.

Get Derivative Securities and Difference Methods PDF

This e-book is dedicated to picking the costs of economic derivatives utilizing a partial differential equation strategy. within the first half the authors describe the formula of the issues (including similar free-boundary difficulties) and derive the closed shape strategies in the event that they were came across. the second one half discusses tips to receive their numerical recommendations successfully for either European-style and American-style derivatives and for either inventory suggestions and rate of interest derivatives.

Download e-book for iPad: Numbers and Computers by Ronald T. Kneusel

This can be a booklet approximately numbers and the way these numbers are represented in and operated on via desktops. it is important that builders comprehend this quarter as the numerical operations allowed via pcs, and the constraints of these operations, particularly within the region of floating element math, impact almost every little thing humans attempt to do with desktops.

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

Sample text

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, ... , n. 12) Inparticular, XPd n{(x,y): xbinary} Proof. Consider any dE =Xforall d = 0,1, ... ,n. {1, ... 5a) are also satisfied. Toward this end, consider any (11 , 1 2 ) of order (d -1), and any r E {l, ... ,R}. 5a) for Next, let us show that conv(X) any ( x, y) E conv(X) ~ ~ Xn.

Consider the following mixed-integer 0-1 constraint region. X={(x,y): x+y~2. -x+y~1. xbinaryandy~O}. 1. 8), although the other defining constraints of X imply the boundedness of y. The RLT process can be applied directly to X as above, without creating any explicit upper bound on y. Notice that for this instance, we have n = 1, and so by our foregoing discussion, the relaxation X1 at level d = 1 should produce the convex hull representation. verify this fact. Let us Sherali and Adams For d 30 = 1, the bound-factor (products) of order 1 are simply x and (1- x).

3. Coping with Large-Scale Representations While the RLT process leads to tight linear programming relaxations for the underlying discrete or continuous nonconvex problems being solved as discussed above, one has to Sherali and Adams 18 contend with the repeated solutions of such large-scale linear programs. linear programs possess a special structure induced by the replicated products of the original problem constraints (or its subset) with certain designated variables. At the same time, this process injects a high level of degeneracy in the problem since blocks of constraints automatically become active whenever the factor expression that generated them turns out to be zero at any feasible solution, and the condition number of the bases can become quite large.

Download PDF sample

A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems by Hanif D. Sherali


by Christopher
4.4

Rated 4.57 of 5 – based on 43 votes