I'm trying to solve a large LP using the Gurobi solver. It has 50K rows and 1.3M columns. NOTE that although the problem is MIP, I want to talk only about solving the simplex at the root node.
I found out that out of these 1.3M variables, there are ~10K variables that when I change their coefficient in the objective, have a dramatic effect on the difficulty of solving the simplex at the root node. If their coefficient is 1 (all with the same coefficient), the simplex is solved within 4 seconds. If their coefficient is 10 (again, all with the same coefficient), Gurobi spends 15 minutes trying to solve the simplex and still doesn't succeed.
Why is this happening? Does it have to do with degeneracy? Ill conditioning? Scale? If you can point out a possible direction to explore it would be great.
cost = 1, simplex finds a solution instantly!
Found heuristic solution: objective 23054.663666
Variable types: 295 continuous, 1278400 integer (1277734 binary)
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
0 6.6627962e+02 1.192000e+03 0.000000e+00 89s
2429 1.3467620e+04 1.137112e+03 0.000000e+00 90s
2973 1.3838855e+04 0.000000e+00 0.000000e+00 91s
Root relaxation: objective 1.383885e+04, 2973 iterations, 4.26 seconds
cost = 10, simplex doesn't find a solution :(
Found heuristic solution: objective 25501.568169
Variable types: 295 continuous, 1278402 integer (1277736 binary)
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
0 1.0812209e+03 1.233188e+03 0.000000e+00 83s
7437 1.8077371e+04 1.554334e+05 0.000000e+00 85s
10137 1.8151933e+04 5.576900e+04 0.000000e+00 90s
11814 1.8207780e+04 1.029386e+05 0.000000e+00 95s
13095 1.8222274e+04 4.753930e+04 0.000000e+00 100s
14319 1.8237355e+04 2.851513e+05 0.000000e+00 105s
15452 1.8250858e+04 9.594756e+04 0.000000e+00 110s...
Ill-conditioning is unlikely to be the culprit, since you are changing objective coefficients and not constraint coefficients. Degeneracy is a possibility. Changing the objective coefficients of a subset of variables may change the simplex solution sequence (if you are using primal simplex) from one portion of the feasible region (where vertices are nondegenerate) to another (where vertices tend to be degenerate). That's a possibility, but by no means a certainty.
I'm not a Gurobi user, but if Gurobi gives you a choice of algorithms for the root relaxation (primal simplex, dual simplex, interior point, ...), you might experiment with changing the algorithm in the difficult case and see if one algorithm gets you better performance. That does not answer the "why" question, but perhaps renders it moot.