Re: [Help-glpk] Linear Programming Relaxation

[Andrew Makhorin]

> 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?