From: Andrew Makhorin <address@hidden>
To: RC Loh <address@hidden>
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
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/