Re: [Help-glpk] Linear Programming Relaxation

[Jeffrey Kantor]

Hi Paul,

As an outside observer to this case, I'm trying to understand
precisely what you're after.  As already mentioned by others, an LP
relaxation finds a lower bound to your problem, while any feasible
integer solution (which may or may not be easy to find) provides an
upper bound.  Solving the problem to integer optimality finds an
actual solution to your problem.

Are you trying to solve your integer/binary problem without imposing
integer/binary constraints?

Jeff

On Sun, Nov 29, 2009 at 8:30 AM, RC Loh <address@hidden> wrote:
> 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/ .
>
>
>
> ________________________________
> Yahoo! Toolbar is now powered with Search Assist. Download it now!
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/help-glpk
>
>