> 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 mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk