Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: weak LP relaxation: Gentle intro for the street person?
Replies: 9   Last Post: Oct 31, 2013 4:37 PM

 Messages: [ Previous | Next ]
 Paul Posts: 517 Registered: 2/23/10
Re: weak LP relaxation: Gentle intro for the street person?
Posted: Oct 31, 2013 4:37 PM

On Thursday, October 31, 2013 4:32:20 PM UTC-4, Ray Vickson wrote:
> I don't think the term "weak LP relaxation" has a formal definition;
> some authors call it just plain LP relaxation. The terminology is an
> add-on to help distinguish the "quality" of various types of
> relaxation, and in this context "weak" typically means "not
> sophisticated, and probably not very effective". So, the starting
> relaxation, obtained by just dropping the adjective "integer" would
> typically be weak. In more technical terms, the LP feasible region
> and the convex hull of the IP feasible region are "very different",
> so the LP solution may not give much insight into the IP solution.
> Various types of cuts have been devised to strengthen the
> relaxation, and that just means trying to make the two regions more
> closely resemble each other.
>
> In the early days of IP or MIP, people tried to develop general
> cutting-plane methods---some one-size-fits-all approaches---and they
> did not work out well in practice (even though they led to provably
> convergent algorithms yielding provably optimal solutions). Some
> types of branch-and-bound became standard for many years.
> Nowadays---for problems in which the old standbys take too long or
> use too many resources--researchers mostly try to develop special
> methods for special problems, by exploiting deep properties of one
> type of problem that may not apply to some other type of problem.
> So, for example, they search for knapsack polytope facets, or
> vehicle-routing facets, or job-shop scheduling facets, etc. But, in
> any case, some LP relaxations are stronger (i.e., better) than
> others, so we might say that one is a weaker relaxation than
> another. As I said already, I don't think there is a formal
> definition---at least there is not one I have ever seen before
> retiring 10 years ago--and I have not seen any since then, either,
> in the few new articles I read occasionally.
>

Thanks. Your explanation would certainly explain the absence of a definition online.

Date Subject Author
10/30/13 Paul
10/30/13 RGVickson@shaw.ca
10/31/13 Paul
10/31/13 fom
10/31/13 RGVickson@shaw.ca
10/31/13 RGVickson@shaw.ca
10/31/13 fom
10/31/13 Paul
10/31/13 RGVickson@shaw.ca
10/31/13 Paul