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

By Hanif D. Sherali

This e-book offers with the speculation 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 different types 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 incentive for this booklet is J J the position of tight linear/convex programming representations or relaxations in fixing such discrete and non-stop nonconvex programming difficulties. The imperative thrust is to begin with a version that offers an invaluable illustration and constitution, after which to additional advance this illustration via automated reformulation and constraint iteration innovations. As pointed out above, the focus of this booklet is the advance and alertness of RL T to be used as an automated reformulation approach, and likewise, to generate robust legitimate inequalities. The RLT operates in levels. within the Reformulation section, 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 for that reason linearized, other than that definite convex constraints are often retained in XV specific specified circumstances, within the Linearization/Convexijication part. this is often performed through the definition of compatible new variables to interchange every one particular 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

Introduction to Bayesian Scientific Computing: Ten Lectures on Subjective Computing

This e-book has been written for undergraduate and graduate scholars in numerous components of arithmetic and its functions. it's for college kids who're keen to get conversant in Bayesian method of computational technological know-how yet now not inevitably to head in the course of the complete immersion into the statistical research.

Numerical Methods for Shallow-Water Flow

A wide selection of difficulties are linked to the circulation of shallow water, resembling atmospheric flows, tides, typhoon surges, river and coastal flows, lake flows, tsunamis. Numerical simulation is an efficient instrument in fixing them and an outstanding number of numerical equipment can be found. the 1st a part of the ebook summarizes the fundamental physics of shallow-water circulation had to use numerical tools less than quite a few stipulations.

Analysis of Low-Speed Unsteady Airfoil Flows

This ebook offers 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 an evidence of raise and thrust new release, airfoil flutter, gust reaction and dynamic stall.

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

Example text

1969, Peterson, 1976, and Floudas and Pardalos, 1987). In particular, Floudas and Pardalos (1987) discuss applications and provide test examples for chemical and mechanical engineering Sherali and Adams 16 problems, Floudas and Visweswaran (1990a,b), and Lasdon et al. (1979) address applications to chemical engineering, and pooling and blending problems, and Shor ( 1989) discusses a related application ·to water treatment and distribution. Various algorithms employing piecewise-linear convex envelopes or minorants (polyhedral underestimating functions), or polyhedral outer-approximations (see Al-Khayyal and Falk, 1983, Floudas and Visweswaran, 1991, Horst and Tuy, 1990, Pardalos and Rosen, 1987, Sherali and Alameddine, 1992, Sherali and Smith, 1995, and Sherali and Tuncbilek, 1995) have been proposed for special cases of such problems.

1. XP! = {(x,y): max{2x + y- 2, x + y -l,x I 2, 0}::; min{x, 2x, (1- x + 2y) I 2, y}}. Writing out the corresponding equivalent linear inequalities and dropping redundant constraints, we obtain XP! 1. 2. : {3, 0::; x::; e2 ,x integer, 0::; y::; e2 }. Sherali and Adams 32 Hence, we have n = m = 2. Let us consider d = 2, so that D =min{n + 1, d} = 2 as well. 9c) fork = 1, 2}. Some comments and illustrations are in order at this point. 4). While the additional inequalities thus generated would possibly yield tighter relaxations for levels 1, ...

The SOS and plant location constraints are used in concert with the knapsack classes of constraints to conduct such logical tests (see Hoffman and Padberg, 1991). In addition, after solving the resultant linear program, if a fractional solution is obtained, then a further strengthening of this LP representation is conducted by fixing variables based on reduced-cost coefficients along with the objective value of a derived heuristic solution, and additional constraints that delete the fractional LP solution are generated.

Download PDF sample

Rated 4.44 of 5 – based on 19 votes