I am using Gurobi to solve a large LP with SOS1 constraints (MILP):
Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (mac64)
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 3119076 rows, 2032775 columns and 6333365 nonzeros
Model fingerprint: 0x855c8063
Model has 446892 SOS constraints
Variable types: 2032775 continuous, 0 integer (0 binary)
Coefficient statistics:
Matrix range [1e-08, 1e+03]
Objective range [1e-02, 9e+03]
Bounds range [0e+00, 0e+00]
RHS range [1e-04, 1e+07]
Presolve removed 2248693 rows and 669948 columns (presolve time = 5s) ...
Presolve removed 2672897 rows and 1094152 columns (presolve time = 10s) ...
Presolve removed 2814218 rows and 1512747 columns (presolve time = 23s) ...
Presolve removed 2820613 rows and 1519174 columns (presolve time = 25s) ...
Presolve removed 2820613 rows and 1519206 columns (presolve time = 39s) ...
Presolve removed 2820613 rows and 1519559 columns (presolve time = 323s) ...
Presolve removed 2815897 rows and 1516923 columns
Presolve time: 323.65s
Presolved: 303179 rows, 515852 columns, 1185283 nonzeros
Presolved model has 243593 SOS constraint(s)
Variable types: 514173 continuous, 1679 integer (1679 binary)
The solver is finding the integer relaxed solution quickly, and then spinning in the branch & bound (or barrier?) method for a very long time, only finding equivalent objective values to the relaxed solution (as well as infeasible solutions):
Solved with primal simplex (primal model)
Root relaxation: objective 5.003962e+08, 49227 iterations, 24.29 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 5.0040e+08 0 10310 - 5.0040e+08 - - 480s
0 0 5.0040e+08 0 10310 - 5.0040e+08 - - 512s
0 2 5.0040e+08 0 10101 - 5.0040e+08 - - 838s
1 2 5.0040e+08 1 8813 - 5.0040e+08 - 38414 1031s
3 2 5.0040e+08 2 8813 - 5.0040e+08 - 12870 1055s
5 2 5.0040e+08 3 8806 - 5.0040e+08 - 7724 1074s
7 2 5.0040e+08 4 8806 - 5.0040e+08 - 5517 1092s
...
22445 2 infeasible 3856 - 5.0040e+08 - 74.8 17630s
22474 2 5.0040e+08 3870 2779 - 5.0040e+08 - 74.9 17643s
22488 2 5.0040e+08 3877 3069 - 5.0040e+08 - 75.1 17653s
22490 2 5.0040e+08 3878 3069 - 5.0040e+08 - 75.0 17660s
22534 2 infeasible 3900 - 5.0040e+08 - 75.6 17667s
22578 2 5.0040e+08 3922 2980 - 5.0040e+08 - 75.9 17674s
22622 1 infeasible 3944 - 5.0040e+08 - 76.1 17684s
22663 2 5.0040e+08 3964 2953 - 5.0040e+08 - 76.3 17691s
Since this particular problem is for testing, I know that the relaxed objective value is also the optimal value of the MILP. (I will be solving larger, more complex problems for which I do not know the optimal value if this test is successful).
My questions are:
(1) Why doesn't the solver accept the solution? There is no solution to accept. The relaxed solution is not integer feasible (if it was, the solver would have stopped immediately).
(2) Is there a way to improve the solution time? The best way to get better performance is to use better formulations. The large number of SOS1 constraints is somewhat worrying. It may be better to use binary variables instead (may require good bounds).