Re: [Help-glpk] Linear Programming Relaxation

From:

RC Loh

Subject:

Date:

Fri, 27 Nov 2009 12:36:41 +0800 (SGT)

Hi Andrew,

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?

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?

3) How do I cite GLPK for a paper conference submission?

Thank you.

Rdgs,

Paul

From: Andrew Makhorin <address@hidden>
To: RC Loh <address@hidden>
Cc: David Bremner <address@hidden>; address@hidden
Sent: Thursday, 26 November 2009 2:48:55
Subject: Re: [Help-glpk] Linear Programming Relaxation

> What does actually "2-approximation" "3-approximation" or
> "6-approximation" means?

See:
http://en.wikipedia.org/wiki/Approximation_algorithm

Have a new Yahoo! Mail account?