Suboptimal termination and unbounded or infeasible solution
AnsweredHey all,
We use the barrier algorithm without Crossover for a relatively large model (see log below). I know that the ranges aren't great, but unfortunately the parameters must be in consistent physical units and they span large scales. We have already optimized the units to reduce the ranges.
This question is actually not about the reason for numerical problems: I am puzzled about several things related to suboptimal terminations, the Barrier algorithm, and unbounded or infeasible solutions:
 The optimizer returns "infeasible or unbounded" even though I have set BarHomogeneous == 1. Why doesn't the optimizer tell me which one it is or how can I find that out? Gurobi also doesn't write the IIS, which I would expect in the case of an infeasible model. Why is that the case?
 The Residual jumps in iteration 224 (probably because of poor numerics), but decreases smoothly afterwards. Why does the barrier algorithm still terminate with a suboptimal solution and not try to solve it?
A very similar model solves and a previous version of this model solved as well, so I am trying to understand the reason for the numerical problems and the failure to solve.
As always, thanks a lot in advance for your constant great help, and best wishes!
Jacob
objective: 19276622 rows, 16452406 columns, 53322217 nonzeros
Set parameter QCPDual to value 1
Set parameter LogFile to value ".//outputs//logs//pyomoLogFile.log"
Set parameter Method to value 2
Set parameter NodeMethod to value 2
Set parameter BarHomogeneous to value 1
Set parameter Crossover to value 0
Gurobi Optimizer version 9.5.1 build v9.5.1rc2 (linux64)
Thread count: 128 physical cores, 128 logical processors, using up to 32 threads
Optimize a model with 19276622 rows, 16452406 columns and 53322217 nonzeros
Coefficient statistics:
Matrix range [1e05, 7e+03]
Objective range [1e+00, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [2e06, 2e+05]
Presolve removed 10810736 rows and 9104770 columns (presolve time = 5s) ...
Presolve removed 11093833 rows and 9110000 columns (presolve time = 10s) ...
Presolve removed 14074946 rows and 12091113 columns (presolve time = 20s) ...
Presolve removed 14074946 rows and 12091113 columns (presolve time = 20s) ...
Presolve removed 14123399 rows and 12161968 columns (presolve time = 25s) ...
Presolve removed 14123399 rows and 12161968 columns
Presolve time: 28.32s
Presolved: 5153223 rows, 4290438 columns, 18695396 nonzeros
Elapsed ordering time = 5s
Elapsed ordering time = 10s
Elapsed ordering time = 15s
Elapsed ordering time = 20s
Elapsed ordering time = 42s
Elapsed ordering time = 45s
Elapsed ordering time = 50s
...
Elapsed ordering time = 1135s
Elapsed ordering time = 1140s
Elapsed ordering time = 1145s
Elapsed ordering time = 1150s
Ordering time: 1152.31s
Barrier statistics:
Dense cols : 2990
Free vars : 2
AA' NZ : 1.485e+09
Factor NZ : 4.057e+09 (roughly 40.0 GB of memory)
Factor Ops : 1.457e+13 (roughly 30 seconds per iteration)
Threads : 32
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 1.79167195e+11 1.05247950e+14 1.18e+06 1.28e+03 4.54e+07 1273s
1 1.72395481e+11 9.93690253e+13 1.08e+06 4.32e+03 4.19e+07 1285s
...
220 6.72983245e+06 6.73512783e+06 1.28e02 3.22e08 4.47e04 7800s
221 6.73003867e+06 6.73515299e+06 1.24e02 3.26e08 4.33e04 7833s
222 6.73014467e+06 6.73518630e+06 1.22e02 3.91e08 4.24e04 7866s
223 6.73030560e+06 6.73520501e+06 1.18e02 4.20e08 4.13e04 7898s
224 1.79167191e+11 1.05247920e+14 1.18e+06 1.28e+03 4.54e+07 7950s
225 1.58705869e+11 7.83745748e+13 9.67e+05 3.46e+03 3.38e+07 7980s
226 1.50712620e+11 6.50770353e+13 9.06e+05 2.87e+03 2.88e+07 8009s
227 1.43844540e+11 5.48520653e+13 8.49e+05 2.42e+03 2.51e+07 8039s
...
421 6.70897104e+06 6.73145665e+06 5.44e02 1.20e08 1.14e03 13695s
422 6.71048587e+06 6.73165076e+06 5.11e02 1.33e08 1.07e03 13727s
423 6.71127767e+06 6.73191061e+06 4.93e02 2.38e08 1.01e03 13756s
424 6.71365876e+06 6.73201624e+06 4.42e02 1.97e08 9.16e04 13785s
425 6.71520379e+06 6.73218199e+06 4.08e02 6.95e08 8.43e04 13815s
Barrier performed 425 iterations in 13815.16 seconds (25835.34 work units)
Suboptimal termination  objective 6.73030560e+06
Warning: unable to write requested result file './/outputs//logs//infeasible_model_IIS.ilp'
The optimization is infeasible or unbounded

Hi Jacob,
This looks like a perfect example of a model with bad numerics (no warnings, but it is a very big model).
I'd first recommend upgrading to the latest version (10.0.1).
If the problem persists, we have a guide: Solver parameters to manage numerical issues.
There are three main sets of parameters to try: Presolve: Aggregate=0; Presolve=0 or 1;
 Tolerance related: e.g. relax BarConvTol, FeasibilityTol (say to 1e4), set NumericFocus. Also see Making the algorithm less sensitive subsection like ScaleFlag or ObjScale).
Also, you don't need to set NodeMethod as you are solving an LP.
Cheers,
David1 
Hi David,
thanks a lot for your quick reply. Jaromił has also already recommended going to v10, however I am running my optimizations on a central computation cluster, where it is not super easy to install new versions  I will keep it in mind though.I will try the parameters (again  it seems like a constant game of enabling and disabling parameters...) and see if it helps.
My main questions weren't actually hinted at how to solve numerically bad model but a) why the homogenous Barrier algorithm doesn't give a definitive answer if the problem is infeasible or unbounded and b) why the barrier algorithm terminates with a suboptimal solution even though the last iterations were smooth.
I thought it was necessary to set NodeMethod = 2, Method = 2, and Crossover = 2 to disable Crossover.
Thanks a lot and Cheers
Jacob0 
Hi Jacob,
I will try the parameters (again  it seems like a constant game of enabling and disabling parameters...) and see if it helps.
Reformulating the problem to avoid large coefficient ranges (you have no warning but they pretty big) is likely to be a longerterm solution.
My main questions weren't actually hinted at how to solve numerically bad model but a) why the homogenous Barrier algorithm doesn't give a definitive answer if the problem is infeasible or unbounded and
The homogenous algorithm is typically better at handling more numerically challenging models on the boundary of infeasibility. But of course, there is no guarantee that this is always the case, there are instances where the standard algorithm is more stable.
b) why the barrier algorithm terminates with a suboptimal solution even though the last iterations were smooth.
In this case, the last iterations were not smooth. The final solution is infeasible as it has a primal violation of the order of 1e02. Crossover typically helps clean this up.
As Jaromił also mentions in this post with similar behaviour: https://support.gurobi.com/hc/enus/community/posts/9130435458193/comments/9136607863953.I thought it was necessary to set NodeMethod = 2, Method = 2, and Crossover = 2 to disable Crossover.
From the docs NodeMethod: "Algorithm used for MIP node relaxations".
Cheers,
David1 
Dear Jacob and David,
I am also having trouble writing an IIS file, and get a similar error as Jacob (Warning: unable to write requested result file 'test.ilp').
I have tried writing this file both by explicitly passing the option
opt.options['ResultFile'] = "test.ilp"
and by passing the option string
results = opt.solve(instance, tee=True, logfile=result_file_path + '/logfile_' + name + '.log', options_string='ResultFile=test.ilp')
Neither of these attempts have worked. Note that while the logfile in the second example is successfully written, the .ilp file is not.
Do either of you have a solution for this problem?
0 
Hi Goran,
Can you try writing the MPS/LP file from Pyomo and then using the Gurobi command to compute the IIS?
I don't know enough about Pyomo to understand why your approach doesn't work.gurobi_cl ResultFile=iis.ilp my_file.mps
Cheers,
David1 
Hi David,
Thank you for the quick response here.
I can happily report that your method works! Thank you for suggesting this!
Also, while deliberately creating an infeasible test model, I stumbled upon another interesting finding: if the model is truly infeasible, then the approach
opt.options['ResultFile'] = "test.ilp"
will also work.
However, if the model is feasible, then I get the (somewhat misleading and cryptic) error message
Warning: unable to write requested result file 'test.ilp'
I mistook this as meaning that there was a mistake, or it didn't work. However, it seems that if the model starts optimizing, then you will just get the warning above.
1
Please sign in to leave a comment.
Comments
6 comments