[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Linear Programming Relaxation
From: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] Linear Programming Relaxation |
Date: |
Fri, 27 Nov 2009 18:11:01 +0300 |
> 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/ .
- [Help-glpk] Linear Programming Relaxation, RC Loh, 2009/11/24
- Re: [Help-glpk] Linear Programming Relaxation, Andrew Makhorin, 2009/11/24
- Re: [Help-glpk] Linear Programming Relaxation, RC Loh, 2009/11/25
- Re: [Help-glpk] Linear Programming Relaxation, David Bremner, 2009/11/25
- Re: [Help-glpk] Linear Programming Relaxation, RC Loh, 2009/11/25
- Re: [Help-glpk] Linear Programming Relaxation, Andrew Makhorin, 2009/11/25
- Re: [Help-glpk] Linear Programming Relaxation, RC Loh, 2009/11/26
- Re: [Help-glpk] Linear Programming Relaxation,
Andrew Makhorin <=
- Re: [Help-glpk] Linear Programming Relaxation, RC Loh, 2009/11/29
- Re: [Help-glpk] Linear Programming Relaxation, Michael Hennebry, 2009/11/29
- Re: [Help-glpk] Linear Programming Relaxation, Andrew Makhorin, 2009/11/29
- Re: [Help-glpk] Linear Programming Relaxation, RC Loh, 2009/11/30
- Re: [Help-glpk] Linear Programming Relaxation, Ali Baharev, 2009/11/30
- Re: [Help-glpk] Linear Programming Relaxation, Andrew Makhorin, 2009/11/30
- Re: [Help-glpk] Linear Programming Relaxation, Jeffrey Kantor, 2009/11/30
- Re: [Help-glpk] Linear Programming Relaxation, Jeffrey Kantor, 2009/11/29