Re: [Help-glpk] Linear Programming Relaxation

[Jeffrey Kantor]

On Mon, Nov 30, 2009 at 4:17 AM, RC Loh <address@hidden> 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 <address@hidden>
> To: RC Loh <address@hidden>
> Cc: address@hidden
> 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!