lp_solve can not get solution

[guanjihou]

Hi guys,
Again I have encountered an interesting problem. For a simple case, I
can get the solution from Matlab, while using lp_solve, it just came
back saying the model is infeasible. It looks like I have dealt with the
bound of all variable correctly. Just curious what is the cause of this
problem. The model is attached as follow. BTW, all variable y are
positive.
/* Objective function */min: +y1 +y2 +y13 +y22 +y23 +y27;
/* Constraints */+Pg1 -21.9298245614 x1 +16.6666666667 x2 +5.26315789474
x3 = 0;+Pg2 +16.6666666667 x1 -33.1045751634 x2 +5.88235294118 x4 +5 x5
+5.55555555555 x6 = 0.217;+5.26315789474 x1 -30.2631578948 x3 +25 x4 =
0.024;+5.88235294118 x2 +25 x3 -59.7285067873 x4 +25 x6 +3.84615384615
x12 = 0.076;+5 x2 -13.3333333333 x5 +8.33333333333 x7 = 0;+5.55555555555
x2 +25 x4 -91.2698412699 x6 +12.5 x7 +25 x8 +4.7619047619 x9
+1.78571428571 x10 +16.6666666667 x28 = 0;+8.33333333333 x5 +12.5 x6
-20.8333333333 x7 = 0.228;+25 x6 -30 x8 +5 x28 = 0.3;+4.7619047619 x6
-18.6147186147 x9 +9.09090909091 x10 +4.7619047619 x11 =
0;+1.78571428571 x6 +9.09090909091 x9 -49.0909090909 x10 +12.5 x17
+4.7619047619 x20 +14.2857142857 x21 +6.66666666666 x22 =
0.058;+4.7619047619 x9 -4.7619047619 x11 = 0;+3.84615384615 x4
-27.5274725275 x12 +7.14285714286 x13 +3.84615384615 x14 +7.6923076923
x15 +5 x16 = 0.112;+x7 +7.14285714286 x12 -7.14285714286 x13 =
0;+3.84615384615 x12 -8.84615384616 x14 +5 x15 = 0.062;+7.6923076923 x12
+5 x14 -22.2377622378 x15 +4.54545454546 x18 +5 x23 = 0.082;+5 x12
-10.2631578947 x16 +5.26315789474 x17 = 0.035;+12.5 x10 +5.26315789474
x16 -17.7631578948 x17 = 0.09;+4.54545454546 x15 -12.2377622378 x18
+7.6923076923 x19 = 0.032;+7.6923076923 x18 -21.978021978 x19
+14.2857142857 x20 = 0.095;+4.7619047619 x10 +14.2857142857 x19
-19.0476190476 x20 = 0.022;+14.2857142857 x10 -64.2857142857 x21 +50 x22
= 0.175;+6.66666666666 x10 +x16 +50 x21 -62.2222222222 x22
+5.55555555555 x24 = 0;+5 x15 +x17 -8.7037037037 x23 +3.7037037037 x24 =
0.032;+5.55555555555 x22 +3.7037037037 x23 -12.2895622896 x24
+3.0303030303 x25 = 0.087;+3.0303030303 x24 -10.4237867396 x25
+2.63157894737 x26 +4.7619047619 x27 = 0;+2.63157894737 x25
-2.63157894737 x26 = 0.035;+x21 +4.7619047619 x25 -11.3095238095 x27
+2.5 x28 +2.38095238095 x29 +1.66666666667 x30 = 0;+16.6666666667 x6 +5
x8 +2.5 x27 -24.1666666667 x28 = 0;+2.38095238095 x27 -4.60317460318 x29
+2.22222222222 x30 = 0.024;+1.66666666667 x27 +2.22222222222 x29
-3.88888888889 x30 = 0.106;+16.6666666667 x1 -16.6666666667 x2 <=
1.3;+16.6666666667 x1 -16.6666666667 x2 >= -1.3;+5.26315789474 x1
-5.26315789474 x3 <= 1.3;+5.26315789474 x1 -5.26315789474 x3 >=
-1.3;+5.88235294118 x2 -5.88235294118 x4 <= 0.65;+5.88235294118 x2
-5.88235294118 x4 >= -0.65;+25 x3 -25 x4 <= 1.3;+25 x3 -25 x4 >= -1.3;+5
x2 -5 x5 <= 1.3;+5 x2 -5 x5 >= -1.3;+5.55555555555 x2 -5.55555555555 x6
<= 0.65;+5.55555555555 x2 -5.55555555555 x6 >= -0.65;+25 x4 -25 x6 <=
0.9;+25 x4 -25 x6 >= -0.9;+8.33333333333 x5 -8.33333333333 x7 <=
0.7;+8.33333333333 x5 -8.33333333333 x7 >= -0.7;+12.5 x6 -12.5 x7 <=
1.3;+12.5 x6 -12.5 x7 >= -1.3;+25 x6 -25 x8 <= 0.32;+25 x6 -25 x8 >=
-0.32;+4.7619047619 x6 -4.7619047619 x9 <= 0.65;+4.7619047619 x6
-4.7619047619 x9 >= -0.65;+1.78571428571 x6 -1.78571428571 x10 <=
0.32;+1.78571428571 x6 -1.78571428571 x10 >= -0.32;+4.7619047619 x9
-4.7619047619 x11 <= 0.65;+4.7619047619 x9 -4.7619047619 x11 >=
-0.65;+9.09090909091 x9 -9.09090909091 x10 <= 0.65;+9.09090909091 x9
-9.09090909091 x10 >= -0.65;+3.84615384615 x4 -3.84615384615 x12 <=
0.65;+3.84615384615 x4 -3.84615384615 x12 >= -0.65;+7.14285714286 x12
-7.14285714286 x13 <= 0.65;+7.14285714286 x12 -7.14285714286 x13 >=
-0.65;+3.84615384615 x12 -3.84615384615 x14 <= 0.32;+3.84615384615 x12
-3.84615384615 x14 >= -0.32;+7.6923076923 x12 -7.6923076923 x15 <=
0.32;+7.6923076923 x12 -7.6923076923 x15 >= -0.32;+5 x12 -5 x16 <=
0.32;+5 x12 -5 x16 >= -0.32;+5 x14 -5 x15 <= 0.16;+5 x14 -5 x15 >=
-0.16;+5.26315789474 x16 -5.26315789474 x17 <= 0.16;+5.26315789474 x16
-5.26315789474 x17 >= -0.16;+4.54545454546 x15 -4.54545454546 x18 <=
0.16;+4.54545454546 x15 -4.54545454546 x18 >= -0.16;+7.6923076923 x18
-7.6923076923 x19 <= 0.16;+7.6923076923 x18 -7.6923076923 x19 >=
-0.16;+14.2857142857 x19 -14.2857142857 x20 <= 0.32;+14.2857142857 x19
-14.2857142857 x20 >= -0.32;+4.7619047619 x10 -4.7619047619 x20 <=
0.32;+4.7619047619 x10 -4.7619047619 x20 >= -0.32;+12.5 x10 -12.5 x17 <=
0.32;+12.5 x10 -12.5 x17 >= -0.32;+14.2857142857 x10 -14.2857142857 x21
<= 0.32;+14.2857142857 x10 -14.2857142857 x21 >= -0.32;+6.66666666666
x10 -6.66666666666 x22 <= 0.32;+6.66666666666 x10 -6.66666666666 x22 >=
-0.32;+50 x21 -50 x22 <= 0.32;+50 x21 -50 x22 >= -0.32;+5 x15 -5 x23 <=
0.16;+5 x15 -5 x23 >= -0.16;+5.55555555555 x22 -5.55555555555 x24 <=
0.16;+5.55555555555 x22 -5.55555555555 x24 >= -0.16;+3.7037037037 x23
-3.7037037037 x24 <= 0.16;+3.7037037037 x23 -3.7037037037 x24 >=
-0.16;+3.0303030303 x24 -3.0303030303 x25 <= 0.16;+3.0303030303 x24
-3.0303030303 x25 >= -0.16;+2.63157894737 x25 -2.63157894737 x26 <=
0.16;+2.63157894737 x25 -2.63157894737 x26 >= -0.16;+4.7619047619 x25
-4.7619047619 x27 <= 0.16;+4.7619047619 x25 -4.7619047619 x27 >=
-0.16;-2.5 x27 +2.5 x28 <= 0.65;+2.5 x27 -2.5 x28 >=
-0.65;+2.38095238095 x27 -2.38095238095 x29 <= 0.16;+2.38095238095 x27
-2.38095238095 x29 >= -0.16;+1.66666666667 x27 -1.66666666667 x30 <=
0.16;+1.66666666667 x27 -1.66666666667 x30 >= -0.16;+2.22222222222 x29
-2.22222222222 x30 <= 0.16;+2.22222222222 x29 -2.22222222222 x30 >=
-0.16;+5 x8 -5 x28 <= 0.32;+5 x8 -5 x28 >= -0.32;+16.6666666667 x6
-16.6666666667 x28 <= 0.32;+16.6666666667 x6 -16.6666666667 x28 >=
-0.32;+1200 Pg1 -y1 <= 0;+3600 Pg1 -y1 <= 288;+7600 Pg1 -y1 <=
1728;+2000 Pg2 -y2 <= 0;+4400 Pg2 -y2 <= 288;+8400 Pg2 -y2 <= 1728;+1200
Pg13 -y13 <= 0;+3600 Pg13 -y13 <= 288;+7600 Pg13 -y13 <= 1728;+2000 Pg22
-y22 <= 0;+4400 Pg22 -y22 <= 288;+8400 Pg22 -y22 <= 1728;+2000 Pg23 -y23
<= 0;+4400 Pg23 -y23 <= 288;+8400 Pg23 -y23 <= 1728;+1200 Pg27 -y27 <=
0;+3600 Pg27 -y27 <= 288;+7600 Pg27 -y27 <= 1728;
/* Variable bounds */-Inf <= Pg1 <= 0.8;-Inf <= Pg2 <= 0.8;-Inf <= Pg13
<= 0.4;-Inf <= Pg22 <= 0.5;-Inf <= Pg23 <= 0.3;-Inf <= Pg27 <= 0.55;x1 =
0;-Inf <= x2 <= 300;-Inf <= x3 <= 300;-Inf <= x4 <= 300;-Inf <= x5 <=
300;-Inf <= x6 <= 300;-Inf <= x7 <= 300;-Inf <= x8 <= 300;-Inf <= x9 <=
300;-Inf <= x10 <= 300;-Inf <= x11 <= 300;-Inf <= x12 <= 300;-Inf <= x13
<= 300;-Inf <= x14 <= 300;-Inf <= x15 <= 300;-Inf <= x16 <= 300;-Inf <=
x17 <= 300;-Inf <= x18 <= 300;-Inf <= x19 <= 300;-Inf <= x20 <= 300;-Inf
<= x21 <= 300;-Inf <= x22 <= 300;-Inf <= x23 <= 300;-Inf <= x24 <=
300;-Inf <= x25 <= 300;-Inf <= x26 <= 300;-Inf <= x27 <= 300;-Inf <= x28
<= 300;-Inf <= x29 <= 300;-Inf <= x30 <= 300;

[William H. Patton]

I think this is the same issue as
http://tech.groups.yahoo.com/group/lp_solve/message/14712
Because you do not simplify your model beforehand, you should at least
carefully round positive and negative reals to the same precision
in order to allow EXACT cancellations.
+4.7619047619 x6 -18.6147186147 x9 *+9.09090909091 x10* +4.7619047619
x11 = 0;
+1.78571428571 x6 *+9.09090909091* x9*-49.0909090909 x10* +12.5 x17
+4.7619047619 x20 +14.2857142857 x21
+16.6666666667 x1 -16.6666666667 x2 <= 1.3;
+16.6666666667 x1 -16.6666666667 x2

Post by guanjihou
= -1.3;

Also you are right at the edge of a known issue that lp_solve cannot
deal with strictly negative constraints. Unfortunately, relaxng the
,<=0; to <= 0.1
does not fix the issue for this case.
It looks like the solution is supposed to be exactly 0.0 when I try
*primal*. But the numerics seem to stumble and cannot quite quit.
The problem then takes a bad pivot anD gets a big negative again. Here i
added 100 to the objective so you can see it wants to be 100.000 ( sign
is opposite for some scale isue).
but cannot qute deal with the noise left from inconsistent rounding.

Objective value -14440.2576858 at iter 164.
Objective value -14439.2349538 at iter 177.
Objective value -14438.8494827 at iter 190.
Objective value -14438.4284584 at iter 203.
Objective value -110.224879977 at iter 216.
Objective value -106.207085014 at iter 229.
Objective value -104.3437357 at iter 242.
Objective value -103.790637245 at iter 255.*
Objective value -101.330812455 at iter 268.
Objective value -54319.953335 at iter 290.*
Objective value -35151.9006729 at iter 303.
...
Objective value -103.085926518 at iter 2091.
Objective value -102.52973595 at iter 2104.
Objective value -101.7804738 at iter 2117.
Objective value -100.339397242 at iter 2130.
Found feasibility by primal simplex after 2136 iter.
Objective value -11773.8512003 at iter 2143.
Objective value 12441.5358589 at iter 2160.

It keeps cycling like this till it gives up at sever numeric difficulties.
Objective value -101.03663701 at iter 32777.
*Objective value -100.463508608 at iter 32790.
Found feasibility by primal simplex after 32800 iter.*
Objective value -8190.17842259 at iter 32803.
Objective value 12944.3058009 at iter 32821.
Objective value 20421.3387636 at iter 32834.
Objective value 284065.231121 at iter 32847.
Objective value 421978.755917 at iter 32860.
bfp_factorize: Resolving 1 singularity at refact 1286, iter 32868
bfp_factorize: Resolving 1 singularity at refact 1286, iter 32868
bfp_factorize: Replacement slack 127 is already basic!
bfp_factorize: Resolving 1 singularity at refact 1286, iter 32868
bfp_factorize: Replacement slack 127 is already basic!
bfp_factorize: Resolving 1 singularity at refact 1286, iter 32868
bfp_factorize: Replacement slack 38 is already basic!
Objective value * 105067325.757 *at iter 32881.
Objective value 148718361.531 at iter 32894.
Objective value 148730333.104 at iter 32907.
Objective value * 148731447.095 *at iter 32920.
The model FAILED



On the other hand if I *mess with your fixed var x1,* I am inclined
to be skeptical of your asserted MATLAB solution.
0 <= Pg27 <= 0.55;
// x1 = 0;
x1 <= 10.246;
0 <= x2 <= 300;
Using PRIMAL simplex for phase 1 and PRIMAL simplex for phase 2.
The primal and dual simplex pricing strategy set to 'Devex'.

Objective value -101.88736 at iter 13.
Objective value -101.702398737 at iter 26.
Objective value -100.282950877 at iter 39.
Found feasibility by primal simplex after 42 iter.
with
x1 = 0.333095
or* x1 <= 0.246;* then obj value is Optimal solution *8153.42*026741
after 44 iter.
Excellent numeric accuracy ||*|| = 3.17801e-015
or from clp
H:\lpsolve-55\glpk445bin>clp guanjihou1.mps remember the 100 added to
the obj is gone. or seems to be a delta of 200? AS lp_solve on the mps
is also 8153.4203...
YES, I remember *clp* interprets the constant in the objective a having
the opposite sign!
Coin LP version 1.03.03, build Nov 8 2006
command line - clp guanjihou1.mps
At line 8 NAME LPSolver
At line 9 ROWS
At line 141 COLUMNS
At line 314 RHS
At line 373 BOUNDS
At line 410 ENDATA
Problem LPSolver has 130 rows, 42 columns and 318 elements
Model was imported from .\guanjihou1.mps in 0.002 seconds
Presolve 108 (-22) rows, 30 (-12) columns and 268 (-50) elements
Perturbing problem by 0.001 % of 15776.2 - largest nonzero change
8.91576e-005
% 5.65139e-007) - largest zero change 9.12957e-005
0 Obj -100 Primal inf 0.132344 (21)
38 Obj 7953.42
Optimal - objective value *7953.42*
After Postsolve, objective 7953.42, infeasibilities - dual 0 (0), primal
0 (0)
Optimal objective 7953.420323 - 38 iterations time 0.012, Presolve 0.00


*H:\lpsolve-55\glpk445bin>*
H:\lpsolve-55\glpk445bin>glpsol guanjihou1.mps
GLPSOL: GLPK LP/MIP Solver, v4.45
Parameter(s) specified in the command line:
guanjihou1.mps
Reading problem data from `guanjihou1.mps'...
Problem: LPSolver
Objective: R0
131 rows, 42 columns, 324 non-zeros
410 records were read
GLPK Simplex Optimizer, v4.45
131 rows, 42 columns, 324 non-zeros
Preprocessing...
129 rows, 42 columns, 316 non-zeros
Scaling...
A: min|aij| = 1.000e+000 max|aij| = 8.400e+003 ratio = 8.400e+003
GM: min|aij| = 1.633e-001 max|aij| = 6.122e+000 ratio = 3.748e+001
EQ: min|aij| = 2.668e-002 max|aij| = 1.000e+000 ratio = 3.748e+001
Constructing initial basis...
Size of triangular part = 120
0: obj = 1.000000000e+002 infeas = 2.201e+001 (9)
* 48: obj = *8.153*420323e+003 infeas = 0.000e+000 (0)
OPTIMAL SOLUTION FOUND
Time used: 0.0 secs
Memory used: 0.2 Mb (185883 bytes)

H:\lpsolve-55\glpk445bin>

William

GLPk does no better. I saved it as a ceplex format with the + 100 in the
objective.

H:\lpsolve-55\glpk445bin>glpsol guanjihou.lpt -lp
Invalid option `-lp'; try glpsol --help

H:\lpsolve-55\glpk445bin>glpsol guanjihou.lpt --lp
GLPSOL: GLPK LP/MIP Solver, v4.45
Parameter(s) specified in the command line:
guanjihou.lpt --lp
Reading problem data from `guanjihou.lpt'...
130 rows, 43 columns, 318 non-zeros
215 lines were read
GLPK Simplex Optimizer, v4.45
130 rows, 43 columns, 318 non-zeros
Preprocessing...
126 rows, 41 columns, 307 non-zeros
Scaling...
A: min|aij| = 1.000e+000 max|aij| = 8.400e+003 ratio = 8.400e+003
GM: min|aij| = 1.633e-001 max|aij| = 6.122e+000 ratio = 3.748e+001
EQ: min|aij| = 2.668e-002 max|aij| = 1.000e+000 ratio = 3.748e+001
Constructing initial basis...
Size of triangular part = 117
0: obj = 1.000000000e+002 infeas = 1.097e+005 (9)
64: obj = 1.079571494e+004 infeas = 4.128e-001 (2)
PROBLEM HAS NO FEASIBLE SOLUTION
glp_simplex: unable to recover undefined or non-optimal solution
Time used: 0.0 secs
Memory used: 0.2 Mb (184482 bytes)

H:\lpsolve-55\glpk445bin>


MPS format does not support the constant in the objective so it does not
go over. The likely solution is 0.

H:\lpsolve-55\glpk445bin>glpsol guanjihou.mps
GLPSOL: GLPK LP/MIP Solver, v4.45
Parameter(s) specified in the command line:
guanjihou.mps
Reading problem data from `guanjihou.mps'...
guanjihou.mps:8: warning: missing model name in field 3
Objective: R0
guanjihou.mps:446: warning: missing final end of line
131 rows, 43 columns, 325 non-zeros
446 records were read
GLPK Simplex Optimizer, v4.45
131 rows, 43 columns, 325 non-zeros
Preprocessing...
126 rows, 41 columns, 307 non-zeros
Scaling...
A: min|aij| = 1.000e+000 max|aij| = 8.400e+003 ratio = 8.400e+003
GM: min|aij| = 1.633e-001 max|aij| = 6.122e+000 ratio = 3.748e+001
EQ: min|aij| = 2.668e-002 max|aij| = 1.000e+000 ratio = 3.748e+001
Constructing initial basis...
Size of triangular part = 117
0: obj = 1.000000000e+002 infeas = 1.097e+005 (9)
73: obj = 8.443163722e+003 infeas = 1.147e-001 (3)
PROBLEM HAS NO FEASIBLE SOLUTION
glp_simplex: unable to recover undefined or non-optimal solution
Time used: 0.0 secs
Memory used: 0.2 Mb (200802 bytes)

H:\lpsolve-55\glpk445bin>

CLP?

H:\lpsolve-55\glpk445bin>clp guanjihou.mps
Coin LP version 1.03.03, build Nov 8 2006
command line - clp guanjihou.mps
At line 8 NAME
At line 9 ROWS
At line 141 COLUMNS
At line 315 RHS
At line 373 BOUNDS
At line 446 ENDATA
Problem no_name has 130 rows, 43 columns and 318 elements
Model was imported from .\guanjihou.mps in 0.01 seconds
Presolve 79 (-51) rows, 15 (-28) columns and 186 (-132) elements
Perturbing problem by 0.001 % of 14301.6 - largest nonzero change
9.9793e-005 (%
1.16296e-006) - largest zero change 8.08381e-005
0 Obj 100 Primal inf 4.88673 (20) Dual inf 6.6797e-005 (1)
19 Obj 26932.7 Primal inf 1.50667 (29)
Primal infeasible - objective value 26932.7
Presolved problem not optimal, resolve after postsolve
After Postsolve, objective 26932.7, infeasibilities - dual 0 (0), primal
6.04214
(19)
0 Obj 26932.7 Primal inf 0.901644 (19)
0 Obj 26932.7 Primal inf 0.901644 (19)
Primal infeasible - objective value 26932.7
PrimalInfeasible objective 26932.66765 - 19 iterations time 0.012,
Presolve 0.01


H:\lpsolve-55\glpk445bin>


On 7/23/2012 7:17 PM, guanjihou wrote:
Again I have encountered an interesting problem. For a simple case, I
can get the solution from Matlab, while using lp_solve, it just came
back saying the model is infeasible. It looks like I have dealt with the
bound of all variable correctly. Just curious what is the cause of this
problem. The model is attached as follow. BTW, all variable y are positive.

Post by guanjihou
/* Objective function */
min: +y1 +y2 +y13 +y22 +y23 +y27;
/* Constraints */
+Pg1 -21.9298245614 x1 +16.6666666667 x2 +5.26315789474 x3 = 0;
+Pg2 +16.6666666667 x1 -33.1045751634 x2 +5.88235294118 x4 +5 x5
+5.55555555555 x6 = 0.217;
+5.26315789474 x1 -30.2631578948 x3 +25 x4 = 0.024;
+5.88235294118 x2 +25 x3 -59.7285067873 x4 +25 x6 +3.84615384615 x12 =
0.076;
+5 x2 -13.3333333333 x5 +8.33333333333 x7 = 0;
+5.55555555555 x2 +25 x4 -91.2698412699 x6 +12.5 x7 +25 x8
+4.7619047619 x9 +1.78571428571 x10 +16.6666666667 x28 = 0;
+8.33333333333 x5 +12.5 x6 -20.8333333333 x7 = 0.228;
+25 x6 -30 x8 +5 x28 = 0.3;
+4.7619047619 x6 -18.6147186147 x9 *+9.09090909091 x10* +4.7619047619
x11 = 0;
+1.78571428571 x6 *+9.09090909091* x9*-49.0909090909 x10* +12.5 x17
+4.7619047619 x20 +14.2857142857 x21
+6.66666666666 x22 = 0.058;

CUT