Suboptimal termination and unbounded or infeasible solution

Answered

Jacob Mannhardt

March 21, 2023 14:57

Hey 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 sub-optimal 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     [1e-05, 7e+03]
  Objective range  [1e+00, 1e+00]
  Bounds range     [0e+00, 0e+00]
  RHS range        [2e-06, 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.28e-02 3.22e-08  4.47e-04  7800s
 221   6.73003867e+06  6.73515299e+06  1.24e-02 3.26e-08  4.33e-04  7833s
 222   6.73014467e+06  6.73518630e+06  1.22e-02 3.91e-08  4.24e-04  7866s
 223   6.73030560e+06  6.73520501e+06  1.18e-02 4.20e-08  4.13e-04  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.44e-02 1.20e-08  1.14e-03  13695s
 422   6.71048587e+06  6.73165076e+06  5.11e-02 1.33e-08  1.07e-03  13727s
 423   6.71127767e+06  6.73191061e+06  4.93e-02 2.38e-08  1.01e-03  13756s
 424   6.71365876e+06  6.73201624e+06  4.42e-02 1.97e-08  9.16e-04  13785s
 425   6.71520379e+06  6.73218199e+06  4.08e-02 6.95e-08  8.43e-04  13815s

Barrier performed 425 iterations in 13815.16 seconds (25835.34 work units)
Sub-optimal termination - objective 6.73030560e+06


Warning: unable to write requested result file './/outputs//logs//infeasible_model_IIS.ilp'

The optimization is infeasible or unbounded

Related to

Comments

6 comments

David Torres Sanchez
Gurobi Staff

March 21, 2023 19:06
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 1e-4), 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,
David
1
Jacob Mannhardt

March 22, 2023 07:23
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
Jacob
0
David Torres Sanchez
Gurobi Staff

March 23, 2023 12:48
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 longer-term 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 1e-02. Crossover typically helps clean this up.
As Jaromił also mentions in this post with similar behaviour: https://support.gurobi.com/hc/en-us/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,
David
1
Goran Durakovic

June 02, 2023 14:58
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
David Torres Sanchez
Gurobi Staff

June 02, 2023 15:50
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,
David
1
Goran Durakovic

June 02, 2023 16:10
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

Didn't find what you were looking for?