GOLP Linear Programming Infeasible Solution

paolo....@gmail.com

unread,

Dec 28, 2021, 1:48:03 PM12/28/21

to or-tools-discuss

Hello everyone,
I'm working on the below LP model OR-Tools (GOLP)
but it comes with unfeasible solution and it seems that problem does not have an optimal solution and the the solver could not solve the problem.

I don't get where is the error, could you help me?
You support is really appreciated

\ Generated by MPModelProtoExporter
\ Name : SimpleLpProgram
\ Format : Free
\ Constraints : 10
\ Variables : 10
\ Binary : 0
\ Integer : 0
\ Continuous : 10
Minimize
Obj: +20 |44542.0|0.3|M10|41062322|
+20 |44542.0|0.2|M10|41062322|
+20 |44542.0|0.1|M10|41062322|
+19 |44541.0|0.3|M10|41062322|
+19 |44541.0|0.2|M10|41062322|
+19 |44541.0|0.1|M10|41062322|
+18 |44540.0|0.3|M10|41062322|
+18 |44540.0|0.2|M10|41062322|
+18 |44540.0|0.1|M10|41062322|
+1e+16 |TYPE|41062322|
Subject to
_1_rhs: +0.5 |44540.0|0.1|M10|41062322| <= 8
_1_lhs: +0.5 |44540.0|0.1|M10|41062322| >= 0
_2_rhs: +0.5 |44540.0|0.2|M10|41062322| <= 8
_2_lhs: +0.5 |44540.0|0.2|M10|41062322| >= 0
_3_rhs: +0.5 |44540.0|0.3|M10|41062322| <= 8
_3_lhs: +0.5 |44540.0|0.3|M10|41062322| >= 0
_4_rhs: +0.5 |44541.0|0.1|M10|41062322| <= 8
_4_lhs: +0.5 |44541.0|0.1|M10|41062322| >= 0
_5_rhs: +0.5 |44541.0|0.2|M10|41062322| <= 8
_5_lhs: +0.5 |44541.0|0.2|M10|41062322| >= 0
_6_rhs: +0.5 |44541.0|0.3|M10|41062322| <= 8
_6_lhs: +0.5 |44541.0|0.3|M10|41062322| >= 0
_7_rhs: +0.5 |44542.0|0.1|M10|41062322| <= 8
_7_lhs: +0.5 |44542.0|0.1|M10|41062322| >= 0
_8_rhs: +0.5 |44542.0|0.2|M10|41062322| <= 8
_8_lhs: +0.5 |44542.0|0.2|M10|41062322| >= 0
_9_rhs: +0.5 |44542.0|0.3|M10|41062322| <= 8
_9_lhs: +0.5 |44542.0|0.3|M10|41062322| >= 0

_10: +1 |44542.0|0.3|M10|41062322|
+1 |44542.0|0.2|M10|41062322|
+1 |44542.0|0.1|M10|41062322|
+1 |44541.0|0.3|M10|41062322|
+1 |44541.0|0.2|M10|41062322|
+1 |44541.0|0.1|M10|41062322|
+1 |44540.0|0.3|M10|41062322|
+1 |44540.0|0.2|M10|41062322|
+1 |44540.0|0.1|M10|41062322|
+1 |TYPE|41062322| = 2703

Bounds
0 <= |44542.0|0.3|M10|41062322| <= 2703
0 <= |44542.0|0.2|M10|41062322| <= 2703
0 <= |44542.0|0.1|M10|41062322| <= 2703
0 <= |44541.0|0.3|M10|41062322| <= 2703
0 <= |44541.0|0.2|M10|41062322| <= 2703
0 <= |44541.0|0.1|M10|41062322| <= 2703
0 <= |44540.0|0.3|M10|41062322| <= 2703
0 <= |44540.0|0.2|M10|41062322| <= 2703
0 <= |44540.0|0.1|M10|41062322| <= 2703
0 <= |TYPE|41062322| <= 2703
End

paolo....@gmail.com

unread,

Dec 28, 2021, 2:10:00 PM12/28/21

to or-tools-discuss

to be correct the solution status is

E1228 20:08:56.658481 15504 linear_solver.cc:1869] No solution exists. MPSolverInterface::result_status_ = MPSOLVER_ABNORMAL

Laurent Perron

unread,

Dec 29, 2021, 4:36:00 AM12/29/21

to or-tools-discuss

You should enable solver output.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/7418f502-8bed-46ad-a8b2-8e59c8652ea1n%40googlegroups.com.

Laurent Perron

unread,

Dec 29, 2021, 4:51:20 AM12/29/21

to or-tools-discuss

This is the glop output:

Solver : GLOP_LINEAR_PROGRAMMING

Dimension : 19 x 10

Initial problem: 19 rows, 10 columns, 28 entries with magnitude in [5.000000e-01, 1.000000e+00]

Objective stats: 10 non-zeros, range [1.800000e+01, 1.000000e+16]

Bounds stats: 21 non-zeros, range [8.000000e+00, 2.703000e+03]

Starting presolve...

SingletonPreprocessor : 1(-18) rows, 9(-1) columns, 9(-19) entries. (0.000037s)

FreeConstraintPreprocessor : 0(-19) rows, 9(-1) columns, 0(-28) entries. (0.000002s)

UnconstrainedVariablePreprocessor : 0(-19) rows, 0(-10) columns, 0(-28) entries. (0.000010s)

Reached fixed point after presolve pass #1

Presolved problem: 0 rows, 0 columns, 0 entries with magnitude in [0.000000e+00, 0.000000e+00]

Objective stats: No objective term. This is a pure feasibility problem.

Bounds stats: All variables/constraints bounds are zero or +/- infinity.

Final unscaled solution:

Primal objective (before moving primal/dual values) = 2.559000000000000E+19

Dual objective (before moving primal/dual values) = 2.559000000000000E+19

Max. primal values move = 0

Max. dual values move = 0

Primal objective (after moving primal/dual values) = 2.559000000000000E+19

Max. rhs perturbation = 0

Max. cost perturbation = 1

Max. primal infeasibility = 0

Max. dual infeasibility = 0

Objective error <= 2.559e+13

The needed cost perturbation is too large !!

status: IMPRECISE

objective: 2.559e+19

iterations: 0

time: 0.000223

deterministic_time: 0

Status : MPSOLVER_ABNORMAL

Objective : 0.000000000000000e+00

BestBound : 0.000000000000000e+00

Iterations : 0

Time : 0.000259

This is the CLP output

Solver : CLP_LINEAR_PROGRAMMING

Dimension : 19 x 10

Coin0506I Presolve 1 (-18) rows, 4 (-7) columns and 4 (-24) elements

Clp0006I 0 Obj 2.5589e+19 Primal inf 144.10003 (1)

Clp0006I 1 Obj 2.5589e+19 Primal inf 0.10002747 (1)

Clp0001I Primal infeasible - objective value 2.5589e+19

Coin0505I Presolved problem not optimal, resolve after postsolve

Coin0511I After Postsolve, objective 2.5589e+19, infeasibilities - dual 0 (0), primal 16.050014 (1)

Clp0032I PrimalInfeasible objective 2.558899972e+19 - 1 iterations time 0.002, Presolve 0.00

Status : MPSOLVER_INFEASIBLE

Objective : 0.000000000000000e+00

BestBound : 0.000000000000000e+00

Iterations : 1

Time : 0.002079

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

Paolo Tofoni

unread,

Dec 29, 2021, 6:39:01 AM12/29/21

to or-tools...@googlegroups.com

I've run it with GLPSOL and I've got the following output :

GLPSOL: GLPK LP/MIP Solver, v4.57
Parameter(s) specified in the command line:
--cpxlp prog.lp -o output.txt
Reading problem data from 'prog.lp'...
prog.lp:62: warning: missing final end of line
19 rows, 10 columns, 28 non-zeros
62 lines were read
GLPK Simplex Optimizer, v4.57
19 rows, 10 columns, 28 non-zeros
Preprocessing...
~ 0: obj = 2.559000000e+19 infeas = 0.000e+00
OPTIMAL SOLUTION FOUND BY LP PREPROCESSOR
Time used: 0.0 secs
Memory used: 0.0 Mb (29985 bytes)
Writing basic solution to 'output.txt'...

output.txt

Problem:
Rows: 19
Columns: 10
Non-zeros: 28
Status: OPTIMAL
Objective: Obj = 2.559e+19 (MINimum)

No. Row name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- ------------- -------------
1 _1_rhs NU 8 8 -2e+16
2 _1_lhs B 8 0
3 _2_rhs NU 8 8 -2e+16
4 _2_lhs B 8 0
5 _3_rhs NU 8 8 -2e+16
6 _3_lhs B 8 0
7 _4_rhs NU 8 8 -2e+16
8 _4_lhs B 8 0
9 _5_rhs NU 8 8 -2e+16
10 _5_lhs B 8 0
11 _6_rhs NU 8 8 -2e+16
12 _6_lhs B 8 0
13 _7_rhs NU 8 8 -2e+16
14 _7_lhs B 8 0
15 _8_rhs NU 8 8 -2e+16
16 _8_lhs B 8 0
17 _9_rhs NU 8 8 -2e+16
18 _9_lhs B 8 0
19 _10 NS 2703 2703 = 1e+16

No. Column name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- ------------- -------------
1 |44542.0|0.3|M10|41062322|
B 16 0 2703
2 |44542.0|0.2|M10|41062322|
B 16 0 2703
3 |44542.0|0.1|M10|41062322|
B 16 0 2703
4 |44541.0|0.3|M10|41062322|
B 16 0 2703
5 |44541.0|0.2|M10|41062322|
B 16 0 2703
6 |44541.0|0.1|M10|41062322|
B 16 0 2703
7 |44540.0|0.3|M10|41062322|
B 16 0 2703
8 |44540.0|0.2|M10|41062322|
B 16 0 2703
9 |44540.0|0.1|M10|41062322|
B 16 0 2703
10 |TYPE|41062322|
B 2559 0 2703

Karush-Kuhn-Tucker optimality conditions:

KKT.PE: max.abs.err = 0.00e+00 on row 0
max.rel.err = 0.00e+00 on row 0
High quality

KKT.PB: max.abs.err = 0.00e+00 on row 0
max.rel.err = 0.00e+00 on row 0
High quality

KKT.DE: max.abs.err = 0.00e+00 on column 0
max.rel.err = 0.00e+00 on column 0
High quality

KKT.DB: max.abs.err = 0.00e+00 on row 0
max.rel.err = 0.00e+00 on row 0
High quality

End of output

I think it's a tolerance problem,after several attempts,

I have increased it by adding the following line to the GLOP solver and now it works.

this.solver.setSolverSpecificParametersAsString("solution_feasibility_tolerance:22");

I thank you for your support!

You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/sVS8HKv3lcA/unsubscribe.
To unsubscribe from this group and all its topics, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEeZkeK6Pf8pCfYEDXz1osJ0SF3%2BX5d2cXP-SUZcNYiBWXA%40mail.gmail.com.

Bruno De Backer

unread,

Jan 5, 2022, 3:40:52 AM1/5/22

to or-tools...@googlegroups.com

Hello Paolo,

The solution value seems to be huge, and I would trust GLOP better than GLPSOL on this one. There is a precision issue with your model. GLOP is particularly careful (you can even say paranoid) with such issues, and it is a bit rude with its answer, even if it computes the solution correctly.

Upon closer inspection, the dynamic range of the coefficients in the cost function is HUGE. There is one coefficient which is 1e16. If you have a way to scale this, it would be a better bet in the long run than changing the tolerance.

BdB

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CAJwoOLYzzHwh8qxLqDmTs8E%3DViy3teARAwgmVkGEsg1BSxOz_Q%40mail.gmail.com.

--

BdB

Paolo Tofoni

unread,

Jan 14, 2022, 11:55:22 AM1/14/22

to or-tools...@googlegroups.com

Hi Bruno,

I followed your suggestion and I was able to scale the coefficients and it works properly.

Thanks a lot relay appreciated.

BR

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CANb4wxx%3D%3D8K%3DANOTv75JwHBCu0FwZiLjeJ38RG_8AMeO%2BUD3bg%40mail.gmail.com.

Bruno De Backer

unread,

Jan 14, 2022, 12:51:33 PM1/14/22

to or-tools...@googlegroups.com

You made my day. I'm really glad it worked. This happens often, especially when matrices are programmatically generated.

BdB

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CAJwoOLbFu6sRuDKZBC6qvABuhD_feqtWOjGjK5GiZL%3DBAycG8A%40mail.gmail.com.