On Mon, Nov 30, 2009 at 4:17 AM, RC Loh <rc_...@yahoo.com.sg> wrote: > Hi Andrew, Jeffrey, Michael, > > Thank you very much for your responses. > > I will read up on Special Ordered Set (SOS) as suggested by Micheal. Because > SOS is new to me. > > > Hi Jeffrey, > > What I am trying to obtain is that though using LPR, the solution > is bounded, but the solution does not satisfy what I need which is > "x1+x2<=1" which means that "x1" and "x2" cannot co-exist together in a > solution. > > Without using LPR, that is, the "x1" and "x2" are binaries, then the > solution obtained by LP is correct. > > However, when I did the LPR, "x1" and "x2" can become "0.5". Though it still > satisfies the constraint "x1+x2<=1", but that is NOT what I want. > > What I want is that "x1" and "x2" CANNOT co-exist together in the solution.
You are observing correct behavior. In this instance, relaxation means that the solver is not using the binary constraints on x1 and x2. This simplifies the problem considerably and provides a lower bound on the objective function you are minimizing. This bound can be very useful. In your application the lower bound means there is nothing you can do to improve bandwidth or reliability. If the result you get is not good enough then you need to change the specification in some way. Enforcing the binary constraints will only give a poorer result. If you don't like bandwidth or reliability you get with the relaxed solution, then you need to re-engineer the specification. This can be very powerful information in many engineering problems. Unfortunately, removing the binary constraint on x1 and x2 means that x1 and x2 can take on any value between 0 and 1, which is what you are observing. If you need for them to be 0 or 1, then you need to enforce the binary constraints. How much the objective increases is problem dependent, but you know it will between the value of the relaxed solution and the value of any feasible solution. That gap may be wide or narrow, depending on your problem. In this case you do have a set of binary variables, x1 and x2, of which only one member can be 1. This is called a Special Ordered Set (SOS) of Type 1. This situation allows for more efficient solution procedures. To the best of my knowledge GLPK doesn't use procedures specific to SOS sets. This may or may not be an important consideration for your problem. The issue of polynomial time algorithms can be a distraction. If your problem is relatively small scale and you are getting solutions quickly, then don't worry about it. More often the bigger issues are whether your model accurately captures the application, the problem is well posed and robust to small modeling error, and if you're getting the accurate answers you need. Don't worry about computational time unless you're sure its a problem. > > And I understand that LP runs in exponential time, however, LPR can run in > polynomial time. > > That is why, I want to use LPR. > > Any suggestion or idea is appreciated. > > Rdgs, > Paul > > > ________________________________ > From: Andrew Makhorin <m...@gnu.org> > To: RC Loh <rc_...@yahoo.com.sg> > Cc: help-glpk@gnu.org > Sent: Monday, 30 November 2009 2:22:36 > Subject: Re: [Help-glpk] Linear Programming Relaxation > >> However, I was pondering for the last 2 days about your response. It >> seems to me that the global bound is not much use for my problem. >> Because the global will give an *upper bound* for the reliability and >> bandwidth which is of no use. A *lower bound* will be more useful. So > > In case of minimization (like yours) optimal solution to LP relaxation > is just an lower bound to the exact integer optimum while an upper bound > is the one defined by any integer feasible solution. That is, the > following condition always holds: > > lower_bound <= exact_optimum <= upper_bound > >> I was trying to formulate the problem to try to get a *lower bound*, >> but until now I am not successful of doing it. > > Once you have solved LP relaxation, you have got an lower bound. > >> Another question if you do not mind. > > No, I don't. > >> Actually the constraint of "x1+x2<=1" is to prevent x1 and x2 to >> co-exists together in the solution. If x1 and x2 are binary, then GLPK >> can produce a good solution. > >> However, if I will to use LPR, then GLPK gave a solution such that x1 >> and x2 *can* co-exists together in the solution, which is not what I >> want. Is there a way to prevent this? That is, even if LPR is used I >> can prevent x1 and x2 to co-exists together in the solution? > > LP relaxation is just an LP problem, where all variables are allowed > to take any *continuous* values, if only they are satisfied to all LP > constraints. You require that x1 + x2 <= 1 but do not require that > x1 and x2 are integer-valued, so why do you surprise that you get > x1 = x2 = 0.5? Aren't these values satisfy to x1 + x2 <= 1? > > > ________________________________ > New Email names for you! > Get the Email name you've always wanted on the new @ymail and @rocketmail. > Hurry before someone else does! _______________________________________________ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
