
Re: weak LP relaxation: Gentle intro for the street person?
Posted:
Oct 31, 2013 4:32 PM


On Thursday, October 31, 2013 12:17:05 PM UTC7, paul.d...@gmail.com wrote: > On Thursday, October 31, 2013 11:01:49 AM UTC4, fom wrote: > > >On 10/31/2013 9:31 AM, Ray Vickson wrote: > > >>On Thursday, October 31, 2013 7:15:17 AM UTC7, Ray Vickson wrote: > > >>> That's odd, When I enter the keywords "LP relaxation" I get > > >>> hundreds of web pages, many being pdf files of lecture notes on > > >>> the topic. Is there something wrong with all of these? Admittedly, > > >>> some of the notes are "advanced", but many others are > > >>> "elementary", so you really can take your pick. > > >>> > > >>> If there is something missing in these sources, you really will > > >>> need to spell out in more detail the nature of your problem. > > >> > > >> For example,look at > > >> http://mcise.uri.edu/sodhi/documents/ipassignments.PDF , which is > > >> very elementary and very exampleoriented. The little document in > > >> http://people.brunel.ac.uk/~mastjjb/jeb/or/lprelax.html gives a bit > > >> of an introduction, but probably does not have nearly enough > > >> material. The document in > > >> http://sma.epfl.ch/~eisenbra/OptInFinance/Slides/Dec2.pdf goes > > >> through an example in gory detail, all at an elementary level. The > > >> slides in > > >> http://www.cs.uiuc.edu/class/sp08/cs473/Lectures/lec23.pdf go > > >> through a simple vertex cover example in great detail at a pretty > > >> introductory level. I could go on and on, but as I said (and I > > >> meant) Google is your friend. > > > > > > Did you look for "weak LP relaxation"? > > > > > > I can see that you spent more time than I. But, I refined my search > > > to "discrete relaxation" "weak LP relaxation" and received far fewer > > > hits. In addition, there seemed to be little which could be called > > > simple. A number of specific algorithms had been named. So, I did > > > some searches on those algorithms. I could find nothing that gave a > > > simple explanation involving those algorithms. > > > > > > As I said, I only spent a few moments. > > > > > > And, I agree, more needs to be expressed concerning the problem the > > > original poster is facing if they hope for any assistance. > > > > You're right, it's "weak LP relaxation" that poses the challenge, not LP relaxation itself. Wikipedia explains relaxation pretty well for integer linear programming (ILP). > > > > The problem context is that of an ILP formulation of a "vehicle routing problem" (VRP). I am new to both. The paper that I'm reading about it is also my impetus for familiarizing myself with ILP, at least at the level of setting up the problem in standard form and mapping the problemspecific constraints to ILP equalities and inequalities. In the context of the VRP, there is reference to a subtour elimination constraint, which I've become just passingly familiar with. I noted a statement of the deeper fact that naive formulation of those constraints yields "weak LP relaxation". Hoping that I can get just an inkling of what is meant and move on with the rest of the paper rather than becoming a expert at this detail. From what I've googled, weak LP relaxations makes the problem harder to solve.
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 addon 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 cuttingplane methodssome onesizefitsall approachesand they did not work out well in practice (even though they led to provably convergent algorithms yielding provably optimal solutions). Some types of branchandbound became standard for many years. Nowadaysfor problems in which the old standbys take too long or use too many resourcesresearchers 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 vehiclerouting facets, or jobshop 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 definitionat least there is not one I have ever seen before retiring 10 years agoand I have not seen any since then, either, in the few new articles I read occasionally.
Anyway: good luck with your reading.

