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 <m...@gnu.org>
To: RC Loh <rc_...@yahoo.com.sg>
Cc: David Bremner <bremner-dated-1260363255.d81...@pivot.cs.unb.ca>;
help-glpk@gnu.org
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
New Email names for you!
Get the Email name you've always wanted on the new @ymail and @rocketmail.
Hurry before someone else does!
http://mail.promotions.yahoo.com/newdomains/sg/minimize
z: -0.067526 x1 -0.443697 x2 -0.245652 x3 -0.039244 x4 -0.170053 x5 -0.107182
x6 -0.164309 x7 -0.079877 x8 -0.083525 x9 -0.042542 x10 -0.149721 x11 -0.073411
x12 -0.062683 x13 -0.041302 x14 -0.090979 x15 -0.046144 x16 -0.025028 x17
subject to
bw: 9 x1 + 8 x2 + 8 x3 + 8 x4 + 8 x5 + 8 x6 + 8 x7 + 8 x8 + 8 x9 + 8 x10 + 8
x11 + 8 x12 + 8 x13 + 8 x14 + 8 x15 + 8 x16 + 8 x17 >= 9
r_1: x1 + x2 <= 1
r_2: x1 + x3 <= 1
r_3: x1 + x4 <= 1
r_4: x1 + x5 <= 1
r_5: x1 + x6 <= 1
r_6: x1 + x7 <= 1
r_7: x1 + x9 <= 1
r_8: x1 + x10 <= 1
r_9: x1 + x11 <= 1
r_10: x1 + x12 <= 1
r_11: x1 + x13 <= 1
r_12: x1 + x14 <= 1
r_13: x1 + x15 <= 1
r_14: x1 + x16 <= 1
r_15: x1 + x17 <= 1
r_16: x2 + x3 <= 1
r_17: x2 + x4 <= 1
r_18: x2 + x5 <= 1
r_19: x2 + x8 <= 1
r_20: x2 + x10 <= 1
r_21: x2 + x12 <= 1
r_22: x2 + x13 <= 1
r_23: x2 + x16 <= 1
r_24: x2 + x17 <= 1
r_25: x3 + x4 <= 1
r_26: x3 + x6 <= 1
r_27: x3 + x7 <= 1
r_28: x3 + x8 <= 1
r_29: x3 + x9 <= 1
r_30: x3 + x10 <= 1
r_31: x3 + x11 <= 1
r_32: x3 + x12 <= 1
r_33: x3 + x14 <= 1
r_34: x3 + x15 <= 1
r_35: x3 + x16 <= 1
r_36: x4 + x5 <= 1
r_37: x4 + x6 <= 1
r_38: x4 + x7 <= 1
r_39: x4 + x8 <= 1
r_40: x4 + x9 <= 1
r_41: x4 + x10 <= 1
r_42: x4 + x11 <= 1
r_43: x4 + x12 <= 1
r_44: x4 + x13 <= 1
r_45: x4 + x14 <= 1
r_46: x4 + x15 <= 1
r_47: x4 + x16 <= 1
r_48: x4 + x17 <= 1
r_49: x5 + x6 <= 1
r_50: x5 + x8 <= 1
r_51: x5 + x9 <= 1
r_52: x5 + x10 <= 1
r_53: x5 + x11 <= 1
r_54: x5 + x12 <= 1
r_55: x5 + x13 <= 1
r_56: x5 + x14 <= 1
r_57: x5 + x16 <= 1
r_58: x5 + x17 <= 1
r_59: x6 + x7 <= 1
r_60: x6 + x8 <= 1
r_61: x6 + x9 <= 1
r_62: x6 + x10 <= 1
r_63: x6 + x11 <= 1
r_64: x6 + x12 <= 1
r_65: x6 + x13 <= 1
r_66: x6 + x14 <= 1
r_67: x6 + x15 <= 1
r_68: x6 + x16 <= 1
r_69: x6 + x17 <= 1
r_70: x7 + x8 <= 1
r_71: x7 + x9 <= 1
r_72: x7 + x10 <= 1
r_73: x7 + x11 <= 1
r_74: x7 + x13 <= 1
r_75: x7 + x14 <= 1
r_76: x7 + x15 <= 1
r_77: x7 + x16 <= 1
r_78: x7 + x17 <= 1
r_79: x8 + x9 <= 1
r_80: x8 + x10 <= 1
r_81: x8 + x12 <= 1
r_82: x8 + x13 <= 1
r_83: x8 + x14 <= 1
r_84: x8 + x15 <= 1
r_85: x8 + x16 <= 1
r_86: x8 + x17 <= 1
r_87: x9 + x10 <= 1
r_88: x9 + x11 <= 1
r_89: x9 + x12 <= 1
r_90: x9 + x13 <= 1
r_91: x9 + x14 <= 1
r_92: x9 + x15 <= 1
r_93: x9 + x16 <= 1
r_94: x9 + x17 <= 1
r_95: x10 + x11 <= 1
r_96: x10 + x12 <= 1
r_97: x10 + x13 <= 1
r_98: x10 + x14 <= 1
r_99: x10 + x15 <= 1
r_100: x10 + x16 <= 1
r_101: x10 + x17 <= 1
r_102: x11 + x12 <= 1
r_103: x11 + x13 <= 1
r_104: x11 + x14 <= 1
r_105: x11 + x15 <= 1
r_106: x11 + x16 <= 1
r_107: x11 + x17 <= 1
r_108: x12 + x13 <= 1
r_109: x12 + x14 <= 1
r_110: x12 + x15 <= 1
r_111: x12 + x16 <= 1
r_112: x12 + x17 <= 1
r_113: x13 + x14 <= 1
r_114: x13 + x15 <= 1
r_115: x13 + x16 <= 1
r_116: x13 + x17 <= 1
r_117: x14 + x15 <= 1
r_118: x14 + x16 <= 1
r_119: x14 + x17 <= 1
r_120: x15 + x16 <= 1
r_121: x15 + x17 <= 1
r_122: x16 + x17 <= 1
bin x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17
End
minimize
z: -0.067526 x1 -0.443697 x2 -0.245652 x3 -0.039244 x4 -0.170053 x5 -0.107182
x6 -0.164309 x7 -0.079877 x8 -0.083525 x9 -0.042542 x10 -0.149721 x11 -0.073411
x12 -0.062683 x13 -0.041302 x14 -0.090979 x15 -0.046144 x16 -0.025028 x17
subject to
bw: 9 x1 + 8 x2 + 8 x3 + 8 x4 + 8 x5 + 8 x6 + 8 x7 + 8 x8 + 8 x9 + 8 x10 + 8
x11 + 8 x12 + 8 x13 + 8 x14 + 8 x15 + 8 x16 + 8 x17 >= 9
r_1: x1 + x2 <= 1
r_2: x1 + x3 <= 1
r_3: x1 + x4 <= 1
r_4: x1 + x5 <= 1
r_5: x1 + x6 <= 1
r_6: x1 + x7 <= 1
r_7: x1 + x9 <= 1
r_8: x1 + x10 <= 1
r_9: x1 + x11 <= 1
r_10: x1 + x12 <= 1
r_11: x1 + x13 <= 1
r_12: x1 + x14 <= 1
r_13: x1 + x15 <= 1
r_14: x1 + x16 <= 1
r_15: x1 + x17 <= 1
r_16: x2 + x3 <= 1
r_17: x2 + x4 <= 1
r_18: x2 + x5 <= 1
r_19: x2 + x8 <= 1
r_20: x2 + x10 <= 1
r_21: x2 + x12 <= 1
r_22: x2 + x13 <= 1
r_23: x2 + x16 <= 1
r_24: x2 + x17 <= 1
r_25: x3 + x4 <= 1
r_26: x3 + x6 <= 1
r_27: x3 + x7 <= 1
r_28: x3 + x8 <= 1
r_29: x3 + x9 <= 1
r_30: x3 + x10 <= 1
r_31: x3 + x11 <= 1
r_32: x3 + x12 <= 1
r_33: x3 + x14 <= 1
r_34: x3 + x15 <= 1
r_35: x3 + x16 <= 1
r_36: x4 + x5 <= 1
r_37: x4 + x6 <= 1
r_38: x4 + x7 <= 1
r_39: x4 + x8 <= 1
r_40: x4 + x9 <= 1
r_41: x4 + x10 <= 1
r_42: x4 + x11 <= 1
r_43: x4 + x12 <= 1
r_44: x4 + x13 <= 1
r_45: x4 + x14 <= 1
r_46: x4 + x15 <= 1
r_47: x4 + x16 <= 1
r_48: x4 + x17 <= 1
r_49: x5 + x6 <= 1
r_50: x5 + x8 <= 1
r_51: x5 + x9 <= 1
r_52: x5 + x10 <= 1
r_53: x5 + x11 <= 1
r_54: x5 + x12 <= 1
r_55: x5 + x13 <= 1
r_56: x5 + x14 <= 1
r_57: x5 + x16 <= 1
r_58: x5 + x17 <= 1
r_59: x6 + x7 <= 1
r_60: x6 + x8 <= 1
r_61: x6 + x9 <= 1
r_62: x6 + x10 <= 1
r_63: x6 + x11 <= 1
r_64: x6 + x12 <= 1
r_65: x6 + x13 <= 1
r_66: x6 + x14 <= 1
r_67: x6 + x15 <= 1
r_68: x6 + x16 <= 1
r_69: x6 + x17 <= 1
r_70: x7 + x8 <= 1
r_71: x7 + x9 <= 1
r_72: x7 + x10 <= 1
r_73: x7 + x11 <= 1
r_74: x7 + x13 <= 1
r_75: x7 + x14 <= 1
r_76: x7 + x15 <= 1
r_77: x7 + x16 <= 1
r_78: x7 + x17 <= 1
r_79: x8 + x9 <= 1
r_80: x8 + x10 <= 1
r_81: x8 + x12 <= 1
r_82: x8 + x13 <= 1
r_83: x8 + x14 <= 1
r_84: x8 + x15 <= 1
r_85: x8 + x16 <= 1
r_86: x8 + x17 <= 1
r_87: x9 + x10 <= 1
r_88: x9 + x11 <= 1
r_89: x9 + x12 <= 1
r_90: x9 + x13 <= 1
r_91: x9 + x14 <= 1
r_92: x9 + x15 <= 1
r_93: x9 + x16 <= 1
r_94: x9 + x17 <= 1
r_95: x10 + x11 <= 1
r_96: x10 + x12 <= 1
r_97: x10 + x13 <= 1
r_98: x10 + x14 <= 1
r_99: x10 + x15 <= 1
r_100: x10 + x16 <= 1
r_101: x10 + x17 <= 1
r_102: x11 + x12 <= 1
r_103: x11 + x13 <= 1
r_104: x11 + x14 <= 1
r_105: x11 + x15 <= 1
r_106: x11 + x16 <= 1
r_107: x11 + x17 <= 1
r_108: x12 + x13 <= 1
r_109: x12 + x14 <= 1
r_110: x12 + x15 <= 1
r_111: x12 + x16 <= 1
r_112: x12 + x17 <= 1
r_113: x13 + x14 <= 1
r_114: x13 + x15 <= 1
r_115: x13 + x16 <= 1
r_116: x13 + x17 <= 1
r_117: x14 + x15 <= 1
r_118: x14 + x16 <= 1
r_119: x14 + x17 <= 1
r_120: x15 + x16 <= 1
r_121: x15 + x17 <= 1
r_122: x16 + x17 <= 1
bounds
0<=x1<=1
0<=x2<=1
0<=x3<=1
0<=x4<=1
0<=x5<=1
0<=x6<=1
0<=x7<=1
0<=x8<=1
0<=x9<=1
0<=x10<=1
0<=x11<=1
0<=x12<=1
0<=x13<=1
0<=x14<=1
0<=x15<=1
0<=x16<=1
0<=x17<=1
End
lpx_read_cpxlp: 123 rows, 17 columns, 261 non-zeros
lpx_read_cpxlp: 17 integer columns, all of which are binary
lpx_read_cpxlp: 129 lines were read
ipp_basic_tech: 0 row(s) and 0 column(s) removed
ipp_reduce_bnds: 1 pass(es) made, 0 bound(s) reduced
ipp_basic_tech: 0 row(s) and 0 column(s) removed
ipp_reduce_coef: 1 pass(es) made, 0 coefficient(s) reduced
lpx_intopt: presolved MIP has 123 rows, 17 columns, 261 non-zeros
lpx_intopt: 17 integer columns, all of which are binary
lpx_adv_basis: size of triangular part = 123
Solving LP relaxation...
0: objval = 0.000000000e+00 infeas = 1.000000000e+00 (0)
1: objval = -6.752600000e-02 infeas = 0.000000000e+00 (0)
* 1: objval = -6.752600000e-02 infeas = 0.000000000e+00 (0)
* 28: objval = -9.664375000e-01 infeas = 0.000000000e+00 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+ 28: mip = not found yet >= -inf (1; 0)
+ 57: mip = -5.508790000e-01 >= -9.664375000e-01 75.4% (10; 0)
+ 85: mip = -5.934180000e-01 >= -7.280825000e-01 22.7% (6; 4)
+ 90: mip = -6.080060000e-01 >= -6.825930000e-01 12.3% (3; 8)
+ 94: mip = -6.080060000e-01 >= tree is empty 0.0% (0; 19)
INTEGER OPTIMAL SOLUTION FOUND
mip_x1= 0.000000
mip_x2= 1.000000
mip_x3= 0.000000
mip_x4= 0.000000
mip_x5= 0.000000
mip_x6= 0.000000
mip_x7= 1.000000
mip_x8= 0.000000
mip_x9= 0.000000
mip_x10= 0.000000
mip_x11= 0.000000
mip_x12= 0.000000
mip_x13= 0.000000
mip_x14= 0.000000
mip_x15= 0.000000
mip_x16= 0.000000
mip_x17= 0.000000
The maximum reliability is 0.753399 with a bandwidth of 16.000000
Press Enter to continue!
lpx_read_cpxlp: 123 rows, 17 columns, 261 non-zeros
lpx_read_cpxlp: 147 lines were read
lpx_interior: original LP problem has 123 rows and 17 columns
lpx_interior: transformed LP problem has 140 rows and 157 columns
lpx_interior: A has 418 non-zeros
lpx_interior: S has 2170 non-zeros (upper triangle)
lpx_interior: minimal degree ordering...
lpx_interior: computing Cholesky factorization...
lpx_interior: U has 5794 non-zeros
lpx_interior: guessing initial point...
Optimization begins...
0: obj = -1.731631825e+00; rpi = 7.9e+00; rdi = 4.9e-01; gap = 6.3e-01
1: obj = -5.196580854e-01; rpi = 1.0e+00; rdi = 4.9e-02; gap = 1.0e+00
2: obj = -5.227116817e-01; rpi = 2.1e-01; rdi = 2.5e-02; gap = 6.1e-01
3: obj = -6.436771531e-01; rpi = 1.0e-01; rdi = 1.2e-02; gap = 4.2e-01
4: obj = -7.601544184e-01; rpi = 2.5e-02; rdi = 4.4e-03; gap = 2.1e-01
5: obj = -8.501360191e-01; rpi = 8.6e-03; rdi = 1.5e-03; gap = 9.8e-02
6: obj = -9.355881835e-01; rpi = 2.1e-03; rdi = 1.6e-04; gap = 2.4e-02
7: obj = -9.627362019e-01; rpi = 2.6e-04; rdi = 1.7e-05; gap = 2.8e-03
8: obj = -9.660661130e-01; rpi = 2.6e-05; rdi = 1.7e-06; gap = 2.8e-04
9: obj = -9.664003600e-01; rpi = 2.6e-06; rdi = 1.7e-07; gap = 2.8e-05
10: obj = -9.664337860e-01; rpi = 2.6e-07; rdi = 1.7e-08; gap = 2.8e-06
11: obj = -9.664371286e-01; rpi = 2.6e-08; rdi = 1.7e-09; gap = 2.8e-07
12: obj = -9.664374629e-01; rpi = 2.6e-09; rdi = 1.7e-10; gap = 2.8e-08
13: obj = -9.664374963e-01; rpi = 2.6e-10; rdi = 1.7e-11; gap = 2.8e-09
OPTIMAL SOLUTION FOUND
prim_ipt_x1= 0.500000
prim_ipt_x2= 0.500000
prim_ipt_x3= 0.500000
prim_ipt_x4= 0.500000
prim_ipt_x5= 0.500000
prim_ipt_x6= 0.500000
prim_ipt_x7= 0.500000
prim_ipt_x8= 0.500000
prim_ipt_x9= 0.500000
prim_ipt_x10= 0.500000
prim_ipt_x11= 0.500000
prim_ipt_x12= 0.500000
prim_ipt_x13= 0.500000
prim_ipt_x14= 0.500000
prim_ipt_x15= 0.500000
prim_ipt_x16= 0.500000
prim_ipt_x17= 0.500000
The max. rel= 0.891965 with a bandwidth= 68.499999(prim) 0.000000(dual)
Press Enter to continue!
_______________________________________________
Help-glpk mailing list
Help-glpk@gnu.org
http://lists.gnu.org/mailman/listinfo/help-glpk
