Infeasible solution to a feasible problem

I am new to optimizing with Gurobi. I am running an operational research problem with some issues in understanding the solution. I tried to test the program with an example problem providing an initial guess which is the actual solution. Despite this, I always get the same number of solutions for all problems. Also, I think the actual number of solutions should be based on if my system is underdetermined or overdetermined. I am not sure how gurobi handles this and how I can determine this for my problem. Since I always end up with the same number of solutions. When I over-constrain my problem to obtain the exact solution, the solver determines the problem to be infeasible. I am trying to understand this same exact thing on wondering how I can improve my system.

The log file:

Gurobi 9.5.1 (win64) logging started Wed Mar 22 13:10:32 2023

Set parameter LogFile to value "Log.txt"
Set parameter Method to value 2
Gurobi Optimizer version 9.5.1 build v9.5.1rc2 (win64)
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Optimize a model with 49 rows, 2852 columns and 207 nonzeros
Model fingerprint: 0xbc0e461b
Variable types: 2813 continuous, 39 integer (39 binary)
Coefficient statistics:
Matrix range [1e-07, 6e+00]
Objective range [1e-02, 1e+08]
Bounds range [1e+00, 1e+00]
RHS range [9e-01, 1e+04]

User MIP start did not produce a new incumbent solution

Found heuristic solution: objective 48.7018342
Found heuristic solution: objective 48.5332180
Variable types: 2813 continuous, 39 integer (39 binary)
Root barrier log...

Ordering time: 0.00s

Barrier statistics:
AA' NZ : 1.320e+02
Factor NZ : 6.010e+02 (roughly 1 MB of memory)
Factor Ops : 1.188e+04 (less than 1 second per iteration)
Threads : 1

Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 1.34421821e+12 -9.00818903e+09 2.09e+03 0.00e+00 2.04e+10 0s
1 1.47060870e+11 2.40935267e+10 7.59e+01 4.86e+07 5.93e+09 0s
2 1.00047856e+10 -1.58636893e+10 2.00e-08 1.12e-03 8.79e+06 0s
3 1.17600564e+06 -1.23203609e+07 2.84e-08 8.94e-08 4.66e+03 0s
4 2.38393161e+04 -9.34488109e+04 2.71e-08 9.30e-04 9.94e+01 0s
5 6.04276191e+04 2.98565037e+04 2.37e-08 5.97e-03 2.52e+02 0s
6* 8.00753610e+06 8.49785563e+06 4.29e-10 2.91e-03 8.51e-02 0s
7* 1.37186385e+10 1.59645865e+10 1.44e-11 2.78e-03 4.65e-05 0s
8* 4.14822190e+10 1.98650594e+11 4.69e-12 5.84e-03 5.42e-05 0s
9* 2.72054753e+10 -1.03106757e+11 4.07e-12 4.20e-02 2.37e-04 0s
10* 1.48192958e+11 4.73060101e+12 1.69e-14 8.97e-02 2.45e-06 0s
11* 1.23372185e+11 9.56727477e+17 3.39e-18 8.09e-02 5.30e-12 0s

Barrier performed 11 iterations in 0.01 seconds (0.00 work units)
Infeasible model

Root relaxation: infeasible, 0 iterations, 0.00 seconds (0.00 work units)

0 0 infeasible 0 48.53322 48.53322 0.00% - 0s

Explored 1 nodes (0 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 12 (of 12 available processors)

Solution count 2: 48.5332 48.7018

Optimal solution found (tolerance 1.00e-04)
Best objective 4.853321803256e+01, best bound 4.853321803256e+01, gap 0.0000%

Mario Ruthmair

Gurobi Staff

March 23, 2023 12:39

Hi Kaushik,

If you want to find out why some model is infeasible, here is an article on that topic.

However, your log output reveals some numerical issues with your model. Here are some general guidelines how to deal with numerical issues.

Although some heuristics found feasible solutions in the beginning, the root relaxation turns out to be infeasible. This should not happen from a theoretical point of view but can happen if the numerics of your model are bad (with respect to the limited machine precision). Note also that the start solution you hand over is not considered as feasible solution to this model.

Here are some suggestions:

Your matrix coefficient range goes down until 1e-7. Note that the feasibility tolerance is by default 1e-6, all bound or constraint violations below this value might be ignored by the solver. You could either decrease this value with the according parameter linked above, or better try to revise, cleanup, and scale the coefficients you are using.
Do you also experience this issue when using the default settings, i.e., not forcing barrier with Method=2?
You could put more emphasis on numerics by using parameter NumericFocus=1 (or 2 or 3).
Also note that for feasible problems the default number of solutions to keep in the solution pool is 10. Only the best 10 solutions found so far are kept and worse ones are discarded. You can control this with parameter PoolSolutions.

Best regards,
Mario

March 23, 2023 14:41

I just want to add that you are using an old Gurobi version. The latest one is 10.0.1 that potentially deals in a better way with numerically challenging models.

Infeasible solution to a feasible problem

Comments

Didn't find what you were looking for?