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.