Re: [Help-glpk] Linear Programming Relaxation

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 <address@hidden>
To: RC Loh <address@hidden>
Cc: 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 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/ .

From:	RC Loh
Subject:	Re: [Help-glpk] Linear Programming Relaxation
Date:	Sun, 29 Nov 2009 21:30:52 +0800 (SGT)