Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University 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 ]
RGVickson@shaw.ca

Posts: 1,655
Registered: 12/1/07
Re: weak LP relaxation: Gentle intro for the street person?
Posted: Oct 31, 2013 4:32 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Thursday, October 31, 2013 12:17:05 PM UTC-7, paul.d...@gmail.com wrote:
> On Thursday, October 31, 2013 11:01:49 AM UTC-4, fom wrote:
>

> >On 10/31/2013 9:31 AM, Ray Vickson wrote:
>
> >>On Thursday, October 31, 2013 7:15:17 AM UTC-7, 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 example-oriented. 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/Dec-2.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 problem-specific 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 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.



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

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.