Re: [Help-glpk] Linear Programming Relaxation

[Andrew Makhorin]

> 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/ .