What is the relation between presolve and the infeasibility of model?
Answered
I'm designing a iteration algorithm in which I need to solve a MILP model during each iteration.Although the initializaion goes well (with warning 'max constraint violation (2.4386e-06) exceeds tolerance'),the question comes as the model turns out infeasible after iteration.
I tries to turn off the presolve function and that works.But new question comes as I find that some variables doesn't observe the constraints I set,which results in the mistake of final objective computing.
I really want to know why the 'presolve' parameter would affect the feasibility of model and whether exites some solutiuons to keep the model feasible and correct.
Thanks in advance!
-
The programme is weitten in Matlab with yalmip.Here are some details:
I have linearized two items of two variables multiplication in order to avoid quardratic models as follows,the result is the linearization of 'xch=rho_ch_max*X' and 'xdis=rho_dis_max*X'.
But if I set the 'presolve' parameter to zero,the result doesn't observe the constraints.
X=binvar(3,96);% boolean variable
xdis=sdpvar(3,96);% continuous variable
xch=sdpvar(3,96);% continuous variable
rho_ch_max=sdpvar(3,96);% continuous variable
rho_dis_max=sdpvar(3,96);% continuous variable
M=1e6;% bid enough constant
Cadj=[Cadj,0<=xch<=M*X,
xch<=rho_ch_max,
xch>=rho_ch_max-M*(1-X),
0<=xdis<=M*X,
xdis<=rho_dis_max,
xdis>=rho_dis_max-M*(1-X)];0 -
Here's the message of infeasible model (when 'presolve' parameter is set to 0):
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time0 0 -2.228e+07 0 309 - -2.228e+07 - - 1s
0 0 -98.96623 0 258 - -98.96623 - - 1s
0 0 -98.95347 0 254 - -98.95347 - - 2s
0 0 -97.98518 0 230 - -97.98518 - - 2s
0 0 -97.78747 0 207 - -97.78747 - - 2sCutting planes:
Learned: 4
Gomory: 126
Cover: 72
Implied bound: 332
Clique: 97
MIR: 101
StrongCG: 6
Flow cover: 705
Inf proof: 1
Network: 19
RLT: 79
Relax-and-lift: 84Explored 1 nodes (27360 simplex iterations) in 2.84 seconds (2.47 work units)
Thread count was 16 (of 16 available processors)Solution count 0
It seems on the brink of a solution and infeasible.
0 -
Hi,
There seem to be some numerical issues in your model related to finite precision arithmetics.
Here are some guidelines for numerical issues, where also the relation to presolve is detailed.Here are a few suggestions:
- Instead of linearizing the quadratic terms by yourself, you could hand over the quadratic model to Gurobi.
- If Gurobi finishes with status "Infeasible", you can try to compute an IIS to find out why the model is infeasible.
- You can play with tolerance parameters, e.g., FeasibilityTol, to see whether the model is at the boundary of (in)feasibility.
Best regards,
Mario0 -
Thanks for the prompt response Mario!
I have tried to reset these parameters:'Aggergate','AggFill' and 'IntFeasTol',but gurobi still finishes 'infeasible'.And after I set the parameter ' FeasibilityTol' to 10^-9 guorbi still finishes with status 'Infeasible'.I have noticed the second tip of 'Models at the edge of infeasibility' that presolve reductions can also play a role.Do you have suggestions to deal with this situation?
0 -
And here's also answers for your three suggestions:
- for suggestion 1, I'm worried about whether quardratic model would deteriorate the efficiency since the solving procedure is in a iteration.Also I used the strong duality theorem and KKT conditions to transfer the initial bi-level model into single level model,in which the model has also been linearized.So it would be regrettable to hand over the quardratic model.
- for suggestion 2,It takes a long time compute IIS(more than 15 minutes).Is there any way to speed up the computing?
- for suggestion 3,I tried to find the boundary and the smallest boundary(10^-9) still finishes with 'infeasible'.
Best regards,
Suyue
0 -
If all the different parameter settings lead to status "infeasible" then probably the model is indeed infeasible.
Yes, computing an IIS can sometimes take a long time but I would consider this as a method to analyze why some model is infeasible so it might be ok to run this once for a few hours. Additionally, you can play with parameter IISMethod and see whether some particular value (0,1,2,3) leads to a faster IIS computation.
You could also try to increase the value of FeasibilityTol and see whether the model gets feasible, e.g., to 1e-5 or even higher.
0 -
Hi Mario
It seems that the model is confronted with severe numeric issues as some warnings prompt after :
- Warning: Model contains large matrix coefficient range
Consider reformulating model or setting NumericFocus parameter
to avoid numerical issues.- Warning: cleanup yields a better solution due to numeric instability
I'm wondering what the second warning means?And also which part would lead to numeric instability(such as the big-M method?）
0 -
As the first warning says, you could try parameter NumericFocus=1 (or 2, 3). But in general you might work on scaling the coefficients to obtain smaller ranges, as also mentioned in the numerics guidelines.
The second warning means that after obtaining a solution to the presolved model, transforming it back to the original model lead to a different solution.
Yes, the Big-M method is classical source for numerical issues since the M is usually a very large value. It is always recommended to use as small M values as possible. Often based on the variable bounds or problem knowledge a much smaller M value can be pre-computed.
0
Please sign in to leave a comment.
Comments
8 comments