The Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   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
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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.
>
> Anyway: good luck with your reading.


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



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2017. All Rights Reserved.