Hi Andrew,
Thank you very much for your response.
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 I was trying to formulate the
problem to try to get a *lower bound*, but until now I am not successful of
doing it.
Another question if you do not mind.
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?
Thanks in advance.
Rdgs,
Paul
________________________________
From: Andrew Makhorin <m...@gnu.org>
To: RC Loh <rc_...@yahoo.com.sg>
Cc: help-glpk@gnu.org
Sent: Friday, 27 November 2009 11:11:01
Subject: Re: [Help-glpk] Linear Programming Relaxation
> Just to clarify on Linear Programming Relaxation.
> I am attempting to solve the NP-hard problem of Optimizing Reliability
> Subject to a Bandwidth Constraint using Linear Programming Relaxation
> and I have created 2 LP files for the problem.
> Test 1: (using Binary structural variables)
> ===============================
> 1) BinaryLinearProgramming_LP_file.txt (see attached file)
> 2) routine lpx_intopt(lp)
> 3) I obtained Output_BinaryLinearProgram.txt (see attached file)
> Test 2: (using bounds structural variables)
> ================================
> 1) LinearProgramRelaxed_LP_file.txt (see attached file)
> 2) routine lpx_interior(lp)
> 3) I obtained Output_LinearProgramRelaxed.txt (see attached file)
> The constraints of "x1+x2<=1" in the LP files is because I do not want
> "x1" and "x2" to be in the solution at the same time because "x1" is
> not edge-disjoint with "x2". Same goes for the rest of the constraints
> in the LP files.
> I have 3 questions:
> 1) The output from the Test 1 using Binary structural variables is
> correct but why I got all "0.5" for all the structural variables in
> the LP Relaxed? Is my formulation of the LP file using the LP
> Relaxation correct?
You get fractional solution, because LinearProgramRelaxed_LP_file
does not constraint variables to be integer-valued unlike
BinaryLinearProgramming_LP_file which does.
> 2) Using the Linear Programming Relaxation (LPR) method to obtain an
> approximate algorithm does not mean that the approximation is for the
> objective function, is that right? Because we cannot guarantee how
> close we are to the optimal result using the LPR, is that right? Using
> the LPR method is more like a heuristics algorithm, is that right?
LPR does not give you an approximation to the exact solution, because
its solution may be fractional (which it is). It only gives you a global
bound to the exact optimum in the sense that optimal objective value
for the original (non-relaxed) problem *cannot* be better than optimal
objective value for LPR.
> 3) How do I cite GLPK for a paper conference submission?
GNU Linear Programming Kit Version X.Y, http://www.gnu.org/software/glpk/ .
Get your new Email address!
Grab the Email name you've always wanted before someone else does!
http://mail.promotions.yahoo.com/newdomains/sg/
_______________________________________________
Help-glpk mailing list
Help-glpk@gnu.org
http://lists.gnu.org/mailman/listinfo/help-glpk