Cannot find an optimal solution with GLOP

[linchu...@gmail.com]

Hi,

I'm using OR-Tools(v9.4) GLOP on python to solve a linear programming problem and I can't reach an optimal solution while the same problem is solvable in Gurobi.

I'm wondering what the problem is and how can I see more output except for only the printed "The problem does not have an optimal solution." 

Thanks!

[Laurent Perron]

This is too vague to be useful. No model, no log...

--
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/117b2fe9-63d1-41de-ac96-9e66b2e87100n%40googlegroups.com.

[linchu...@gmail.com]

Sorry for the insufficient information. But I'm not sure how to view the detail GLOP output so that I can't tell how many variables and constraints are there. 

I've tried  EnableOutput() but nothing came out. Below is my codes, hope it may help.

---------------------------------------------------------------------------

solver = pywraplp.Solver.CreateSolver('GLOP')

solver.EnableOutput()

# Adding variables and  constraints 

...

#obj. function

solver.Minimize(sum(var1[j] for j in range(19*45))
               +sum( var2 [j] for j in range(19*45))
               +sum( var3  [j] for j in range(19*10))
               +sum(var4[j] for j in range(19*10))

               +sum(var5 [j]+var6[j] for j in range(380))

               +10**1*sum(X[j]+Y[j] for j in range(380))
               +10**1*sum(X_diff[j] for j in range(19*10))
               +10**1*sum(Y_diff[j] for j in range(19*10)))

#optimization
status = solver.Solve()

if status == pywraplp.Solver.OPTIMAL:
    print('Solution:')
    print('Objective value =', solver.Objective().Value())
    print('p =', p.solution_value())

else:
   print('The problem does not have an optimal solution.')

laurent...@gmail.com 在 2022年10月20日 星期四下午3:35:08 [UTC+8] 的信中寫道：

[Laurent Perron]

What is the status after solve ?

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/13b5ef51-d82b-4109-ab22-2efe3a1b8bb7n%40googlegroups.com.

[linchu...@gmail.com]

Hi,

I tried to use spyder to run my code and I finally see the output. It shows that "WARNING: Logging before InitGoogleLogging() is written to STDERR
E1024 11:29:51.718339 22936 linear_solver.cc:1879] No solution exists. MPSolverInterface::result_status_ = MPSOLVER_ABNORMAL"

I still can't understand why the LP is unsolvable while an optimal solution can be found by Gurobi.

laurent...@gmail.com 在 2022年10月20日 星期四下午6:20:24 [UTC+8] 的信中寫道：

[Laurent Perron]

Glop is more pedantic with numerical errors. 

Can you generate a mps file and send it to us?

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/9bde62ae-e92a-4125-b3da-d59050ec9228n%40googlegroups.com.

[linchu...@gmail.com]

mps file as attached. The problem is with 7980 Constraints and 3991 Variables

I find from another discussion saying that ABNORMAL status means that the solution does not satisfy the tolerance guarantee during solution verification. Can try to change the verification tolerance or disable them to solve the problem.

However, I didn't figure out how to adjust the tolerance. If it is a need to solve my problem, can I ask for an instruction to do it.

Appreciated for your support!!

laurent...@gmail.com 在 2022年10月24日 星期一下午1:17:55 [UTC+8] 的信中寫道：

[linchu...@gmail.com]

A quick update, I have added the following line to the GLOP solver and now it works.

solver.SetSolverSpecificParametersAsString("solution_feasibility_tolerance:22")

But the solution is different from Gurobi, is it because of the difference tolerance? ( primal and dual feasibility tolerances in Gurobi are 1e-6)

linchu...@gmail.com 在 2022年10月24日 星期一晚上11:55:46 [UTC+8] 的信中寫道：

[harryh...@gmail.com]

This is too vague to be useful. No model, no log..

[Laurent Perron]

Here are the log from GLOP

File        : '/usr/local/google/home/lperron/tmp/ABNORMAL.mps'

Solver      : GLOP_LINEAR_PROGRAMMING

Parameters  : 

Dimension   : 7980 x 3991

Initial problem: 7980 rows, 3991 columns, 15952 entries with magnitude in [1.047850e-17, 1.486980e+02]

Objective stats: 3990 non-zeros, range [1.000000e+00, 1.000000e+01]

Bounds stats: 7978 non-zeros, range [-1.258000e+00, 1.178670e+00]

Starting presolve...

SingletonPreprocessor                        : 7972(-8) rows, 3991(0) columns, 15944(-8) entries. (0.000425s)

UnconstrainedVariablePreprocessor            : 7972(-8) rows, 3987(-4) columns, 15944(-8) entries. (0.000815s)

Reached fixed point after presolve pass #1

DualizerPreprocessor                         : 3987(-3993) rows, 11958(7967) columns, 19930(3978) entries. (0.001954s)

SingletonPreprocessor                        : 3987(-3993) rows, 7972(3981) columns, 15944(-8) entries. (0.001049s)

ScalingPreprocessor                          : 3987(-3993) rows, 7972(3981) columns, 15944(-8) entries. (0.001192s)

Presolved problem: 3987 rows, 7972 columns, 15944 entries with magnitude in [6.353304e-02, 1.000000e+00]

Objective stats: 7970 non-zeros, range [-7.048579e+08, 8.143695e+08]

Bounds stats: 3986 non-zeros, range [1.053167e-09, 6.777498e+09]

Starting basis: create from scratch.

Trying to remove 1 fixed variables from the initial basis.

The matrix with slacks has 3987 rows, 11959 columns, 19931 entries.

Number of basic infeasible variables: 0

Number of basic slack variables: 3986

Number of basic variables at bound: 1

Number of basic fixed variables: 0

Number of basic free variables: 0

Number of super-basic variables: 0

Primal feasibility phase, iteration # 0, sum_primal_infeasibilities = 0.000000000000000E+00

Current status: PRIMAL_FEASIBLE

Primal infeasibility (bounds) = 0

Primal residual |A.x - b| = 0

Dual infeasibility (reduced costs) = 5.47555e+07

Dual residual |c_B - y.B| = 0

Primal optimization phase, iteration # 0, objective = 2.166663000000000E-01

Primal optimization phase, iteration # 77, objective = 5.859246731688636E+00

Primal optimization phase, iteration # 152, objective = 1.157811027372234E+01

Primal optimization phase, iteration # 229, objective = 1.665010393703341E+01

Primal optimization phase, iteration # 294, objective = 2.096106325636621E+01

Primal optimization phase, iteration # 359, objective = 2.476585399119735E+01

Primal optimization phase, iteration # 424, objective = 2.768750630870594E+01

Primal optimization phase, iteration # 489, objective = 3.251573976039086E+01

Primal optimization phase, iteration # 554, objective = 3.694353952087800E+01

Primal optimization phase, iteration # 619, objective = 4.196447760885179E+01

Primal optimization phase, iteration # 684, objective = 4.772640477731304E+01

Primal optimization phase, iteration # 749, objective = 5.393472139042914E+01

Primal optimization phase, iteration # 814, objective = 5.893309607711372E+01

Primal optimization phase, iteration # 879, objective = 6.556286332749903E+01

Primal optimization phase, iteration # 944, objective = 7.194070640783407E+01

Primal optimization phase, iteration # 1009, objective = 7.727789266253991E+01

Primal optimization phase, iteration # 1074, objective = 8.311508483237778E+01

Primal optimization phase, iteration # 1139, objective = 8.970219207077051E+01

Primal optimization phase, iteration # 1204, objective = 9.611806340416801E+01

Primal optimization phase, iteration # 1269, objective = 1.037327100352261E+02

Primal optimization phase, iteration # 1334, objective = 1.096864490609356E+02

Primal optimization phase, iteration # 1399, objective = 1.155757597651018E+02

Primal optimization phase, iteration # 1464, objective = 1.211313370219613E+02

Primal optimization phase, iteration # 1529, objective = 1.268441455722198E+02

Primal optimization phase, iteration # 1594, objective = 1.313178555554478E+02

Primal optimization phase, iteration # 1659, objective = 1.373356375843381E+02

Primal optimization phase, iteration # 1724, objective = 1.423623202754650E+02

Primal optimization phase, iteration # 1789, objective = 1.462726544786358E+02

Primal optimization phase, iteration # 1854, objective = 1.516326183446242E+02

Primal optimization phase, iteration # 1916, objective = 1.565300797388324E+02

Current status: OPTIMAL

Primal infeasibility (bounds) = 0

Primal residual |A.x - b| = 2.11969e-06

Dual infeasibility (reduced costs) = 9.92728e-09

Dual residual |c_B - y.B| = 5.29396e-23

OPTIMAL was reported, yet one of the residuals is above the solution feasibility tolerance after the shift/perturbation are removed.

Final unscaled solution:

Primal objective (before moving primal/dual values) = 1.565300797388324E+02

Dual objective (before moving primal/dual values) = 1.565300797388324E+02

Primal objective (after moving primal/dual values) = 1.565300797388324E+02

Max. rhs perturbation = 3.18023

Max. cost perturbation = 2.75335e-14

Max. primal infeasibility = 3.18023

Max. dual infeasibility = 2.75335e-14

Objective error <= 0.01425

status: IMPRECISE

objective: 156.53

iterations: 1916

time: 0.289853

deterministic_time: 0.159527

Status      : MPSOLVER_ABNORMAL

Objective   : 0.000000000000000e+00

BestBound   : 0.000000000000000e+00

StatusString: 

Time        : 0.3068 s

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

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/e6cfe93a-c842-4380-9d5c-2ecbda2259afn%40googlegroups.com.

[Laurent Perron]

CLP returns 

Status      : MPSOLVER_OPTIMAL

Objective   : 1.951530807612094e+02

BestBound   : 0.000000000000000e+00

StatusString: 

Time        : 0.5096 s

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

[Laurent Perron]

If you want to ignore the numerical check, you can just set the parameter 

change_status_to_imprecise:false

But your problem is very badly conditioned. I suggest you reduce the range of coefficients, or rhs.

Le mar. 25 oct. 2022 à 08:46, linchu...@gmail.com <linchu...@gmail.com> a écrit :

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/e6cfe93a-c842-4380-9d5c-2ecbda2259afn%40googlegroups.com.

--

--Laurent

[linchu...@gmail.com]

Thanks a lot for the detail output and suggestion! 

 I'm wondering that "Ignore the numerical check" you mentioned means to ignore the tolerance of the duality gap, the primal infeasibilities, and the dual infeasibilities? And what is the difference between using change_status_to_imprecise:false and  solution_feasibility_tolerance?

laurent...@gmail.com 在 2022年10月25日 星期二下午3:51:48 [UTC+8] 的信中寫道：