High instability of an MIP

cedric chauve

Sep 5, 6:54 AM PDT

I am using Gurobi (through the python API) to solve a problem aimed at selecting a subset of edges in a graph.

I define these variables as follows:
E_VAR = {}
for e in G_INPUT_EDGES:
E_VAR[e] = ILP_PDG.addVar(vtype=GRB.BINARY,name='E_VAR['+str(e)+']')

I also define a variable counting the number of selected edges:
ES_VAR = ILP_PDG.addVar(vtype=GRB.INTEGER,name='ES_VAR')
ES_CONST = ILP_PDG.addLConstr(ES_VAR,GRB.EQUAL,quicksum(E_VAR[e] for e in G_INPUT_EDGES),'ES_CONST')

When I obtain a solution, I find that the number of edge variables having value 1 is sometimes different (depending on the runs, all with the same parameters) from the value of the variable ES_VAR.

Here is the code I use to visualize both values after the optimization is finished:
NBE = 0
for e in G_INPUT_EDGES:
if E_VAR[e].getAttr(GRB.Attr.X)==1:
NBE+=1
print('DEBUG: value of ES_VAR',ES_VAR.getAttr(GRB.Attr.X))
print('DEBUG: number of E_VAR[e] with value 1 ',NB_E)

Below are the results of two runs, started with the same input and parameters:

Run 1 (observed discrepancy):

Optimal solution found (tolerance 1.00e-04)
Warning: max constraint violation (5.4131e-06) exceeds tolerance
Best objective 2.021999996430e+03, best bound 2.022000000000e+03, gap 0.0000%
DEBUG: value of ES_VAR 989.0
DEBUG: number of E_VAR[e] with value 1 975

Run 2 (worked fine):

Optimal solution found (tolerance 1.00e-04)
Best objective 2.022000000000e+03, best bound 2.022000000000e+03, gap 0.0000%
DEBUG: value of ES_VAR 989.0
DEBUG: number of E_VAR[e] with value 1 989

There seems to be some numerical instability causing the issue. The MIP is quite large (see below) but I see no clear reason for this behaviour.

Academic license - for non-commercial use only
Optimize a model with 5160 rows, 14464 columns and 37616 nonzeros
Model has 7170 general constraints
Variable types: 0 continuous, 14464 integer (12204 binary)
Coefficient statistics:
Matrix range [1e+00, 8e+00]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 5e+03]

Concurrent MIP optimizer: 4 concurrent instances (8 threads per instance)

Presolve added 7230 rows and 0 columns
Presolve removed 0 rows and 8548 columns
Presolve time: 0.38s
Presolved: 12390 rows, 5916 columns, 55199 nonzeros
Variable types: 0 continuous, 5916 integer (5915 binary)

Any help would be welcome

cedric chauve

正式なコメント

Simranjit Kaur

Gurobi Staff

2024年12月06日 00:54

This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.

Eli Towle

2019年09月05日 20:27 編集済み

Hi Cedric,

I suspect the issue is caused by this conditional statement:

if E_VAR[e].getAttr(GRB.Attr.X)==1:

For numerical reasons, Gurobi uses a tolerance to determine whether or not a variable is "close enough" to an integer to be considered an integer. In Gurobi 8.1, this tolerance by default is 1e-5. So, it may be possible that some of the selected edges actually take on a value slightly less than 1 at the optimal solution. Thus, it may work to instead check if the X attribute of the variable lies within this tolerance:

if E_VAR[e].X > 1 - 1e-5:

As to why you are experiencing differences between optimization runs, concurrent MIP optimization is not deterministic (see here).

Lastly, a few notes about the code:

It isn't necessary to specify ES_VAR as an integer variable; ES_VAR is equal to the sum of binary variables, which is always an integer
You can query the X attribute of the Var object directly (e.g., E_VAR[e].X)
You might find the Model.addVars() method well-suited for adding multiple variables all at once

I hope this helps. Thanks!

Eli

2019年09月06日 11:53

Thanks Eli

Your hint on the tolerance was what I needed for my first point.

I tried to run again my ILP not using the concurrent method, and even fixing the seed, but I still do not obtain the same answer at each run. The two parameters I did set specifically are

ILP_PDG.setParam(GRB.Param.Method,4)
ILP_PDG.setParam(GRB.Param.Seed,1)

I did read that this might be due to issue with Presolving, but when I set

ILP_PDG.setParam(GRB.Param.PreSolve,0)

I obtain a segmentation fault.

2019年10月07日 17:36 編集済み

Thanks for reporting this issue. This has been fixed in Gurobi 9.0, scheduled for release this fall.

High instability of an MIP

コメント

お探しのものを見つけられませんでしたか？