Infeasible solution to a feasible problem
Awaiting user inputI 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 overconstrain 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 [1e07, 6e+00]
Objective range [1e02, 1e+08]
Bounds range [1e+00, 1e+00]
RHS range [9e01, 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.00e08 1.12e03 8.79e+06 0s
3 1.17600564e+06 1.23203609e+07 2.84e08 8.94e08 4.66e+03 0s
4 2.38393161e+04 9.34488109e+04 2.71e08 9.30e04 9.94e+01 0s
5 6.04276191e+04 2.98565037e+04 2.37e08 5.97e03 2.52e+02 0s
6* 8.00753610e+06 8.49785563e+06 4.29e10 2.91e03 8.51e02 0s
7* 1.37186385e+10 1.59645865e+10 1.44e11 2.78e03 4.65e05 0s
8* 4.14822190e+10 1.98650594e+11 4.69e12 5.84e03 5.42e05 0s
9* 2.72054753e+10 1.03106757e+11 4.07e12 4.20e02 2.37e04 0s
10* 1.48192958e+11 4.73060101e+12 1.69e14 8.97e02 2.45e06 0s
11* 1.23372185e+11 9.56727477e+17 3.39e18 8.09e02 5.30e12 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)
Nodes  Current Node  Objective Bounds  Work
Expl Unexpl  Obj Depth IntInf  Incumbent BestBd Gap  It/Node Time
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.00e04)
Best objective 4.853321803256e+01, best bound 4.853321803256e+01, gap 0.0000%

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 1e7. Note that the feasibility tolerance is by default 1e6, 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,
Mario0 
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.
0
Please sign in to leave a comment.
Comments
2 comments