Download e-book for iPad: 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 publication offers with the speculation and functions 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 sorts 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 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 significant thrust is to start with a version that offers an invaluable illustration and constitution, after which to additional improve this illustration via computerized reformulation and constraint iteration concepts. 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 strategy, and in addition, to generate powerful 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 for this reason linearized, other than that convinced convex constraints are often retained in XV specific unique situations, within the Linearization/Convexijication section. this is often performed through the definition of appropriate new variables to exchange each one distinctive 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

Get Statistical and Computational Inverse Problems (Applied PDF

This e-book covers the statistical mechanics method of computational answer of inverse difficulties, an leading edge sector of present learn with very promising numerical effects. The innovations are utilized to a few genuine international functions reminiscent of constrained attitude tomography, photo deblurring, electical impedance tomography, and biomagnetic inverse difficulties.

Matematica Numerica Esercizi, Laboratori e Progetti - download pdf or read online

L. a. Matematica Numerica è una disciplina che si sviluppa in simbiosi con il calcolatore. Questo testo propone, oltre a richiami degli argomenti fondamentali, sia Esercizi teorici da risolvere "con carta e penna'', atti a miles comprendere meglio al lettore los angeles teoria, sia Laboratori, in cui in line with un dato problema si debbono scegliere gli algoritmi più adatti, realizzare un programma in linguaggio Matlab in keeping with l. a. loro implementazione, infine rappresentare, interpretare ed analizzare alla luce della teoria i risultati numerici.

An Introduction to Modern Mathematical Computing: With - download pdf or read online

Thirty years in the past mathematical, instead of utilized numerical, computation used to be tough to accomplish and so fairly little used. 3 threads replaced that: the emergence of the non-public laptop; the invention of fiber-optics and the ensuing improvement of the fashionable net; and the development of the 3 “M’s” Maple, Mathematica and Matlab.

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

Example text

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.

D. 1) as equalities by using slack variables. In this chapter, we present the basic construction process of the ReformulationLinearization Technique (RLT). 1), given any level {0, ... , n}, this technique first converts the constraint set into a polynomial mixed- integer zero-one set of restrictions by multiplying the constraints with some suitable ~ degree polynomial factors involving the n binary variables and their complements, and subsequently linearizes the resulting problem through appropriate variable transformations.

To view their relaxations as Balas' hull relaxations requires manipulating the representation at any stage d to write it as a conjunction of a non-standard set of disjunctions. Moreover, by the nature of the RLT approach, Sherali and Adams also show (see Chapter 2) how one can readily construct a hierarchy of linear relaxations leading to the convex hull representation for mixed-integer zero-one polynomial programming problems having no cross-product terms among continuous variables, an important result not shared by the earlier disjunctive work.

Download PDF sample

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


by John
4.1

Rated 4.81 of 5 – based on 11 votes