Confused by Gurobi's primal simplex algorithm

Specific Domains Optimization (Mathematical)
1

I have some my own understanding about the primal simplex algorithm and the dual simplex algorithm.

(Suppose the original primal-side problem is min-cost.) For the primal simplex algorithm, the idea is to maintain primal-side feasibility, while decreasing the objective value by making a series of “pivots”. So I think it should be a monotonically descending algorithm.

In the following logging (Method=0), I can see that the Primal Inf. column is kept zero, which is normal. But I find it confusing to see the ascending trend in the Objective column.

julia> JuMP.optimize!(m)
Gurobi Optimizer version 13.0.1 build v13.0.1rc0 (linux64gpu - "Ubuntu 24.04.4 LTS")

CPU model: AMD EPYC 7763 64-Core Processor, instruction set [SSE2|AVX|AVX2]
Thread count: 128 physical cores, 256 logical processors, using up to 1 threads

Non-default parameters:
TimeLimit  3600
Method  0
Threads  1

Optimize a model with 27130000 rows, 26850006 columns and 268040000 nonzeros (Min)
Model fingerprint: 0x3e56b285
Model has 2430004 linear objective coefficients
Coefficient statistics:
  Matrix range     [8e-06, 1e+00]
  Objective range  [3e-05, 2e+00]
  Bounds range     [3e-01, 7e+01]
  RHS range        [2e-08, 2e+01]

Presolve removed 14768260 rows and 15215409 columns (presolve time = 737s)...
Presolve removed 15238260 rows and 15215409 columns
Presolve time: 888.69s
Presolved: 1990006 rows, 6783379 columns, 48577129 nonzeros

Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0    3.3389239e+00   0.000000e+00   2.624059e+06    898s
  156241    9.3136101e+00   0.000000e+00   2.314513e+06    902s
  188248    9.3136101e+00   0.000000e+00   1.655978e+06    907s
  316533    1.4095379e+02   0.000000e+00   1.043175e+06    911s
  444818    2.7018109e+02   0.000000e+00   1.162103e+07    915s
  547446    3.0251879e+02   0.000000e+00   2.636596e+07    921s
  624417    3.0888606e+02   0.000000e+00   1.315682e+07    926s
  675731    3.1186138e+02   0.000000e+00   2.118484e+06    930s
  752702    3.1623731e+02   0.000000e+00   3.198632e+05    936s
  829673    3.1783697e+02   0.000000e+00   1.941797e+05    942s
  875904    3.1805901e+02   0.000000e+00   4.341262e+05    949s
  885004    3.1806815e+02   0.000000e+00   5.826430e+02    957s
  885394    3.1806895e+02   0.000000e+00   2.925393e+01    964s
  885584    3.1806947e+02   0.000000e+00   1.790597e+02    972s
  885744    3.1806979e+02   0.000000e+00   2.396127e+00    980s
  885899    3.1806704e+02   1.228414e-03   0.000000e+00    995s
  885971    3.1806701e+02   0.000000e+00   2.164037e-02   1055s

Extra simplex iterations from dual to original model: 1713
  887684    3.1806631e+02   0.000000e+00   0.000000e+00   1065s

Solved in 887684 iterations and 1065.47 seconds (5317.67 work units)
Optimal objective  3.180663093e+02

User-callback calls 708, time in user-callback 0.00 sec

It turns out that the twist is that it appears that Gurobi stealthily dualized my original model (to a maximization dual formulation) internally and employed a dual simplex algorithm to tackle that new formulation. (I’m not sure if my speculation here is true.)

It looks pretty weird to me. Because the basic motivation for me to set Method=0 is that I hope the algorithm can find a sequence of (primal) feasible solutions along the iterations (and correspondingly a sequence of descending (suboptimal) objective values).

I don’t think Gurobi’s behavior here is “honest” :neutral_face:

2

Gurobi isn’t trying to be an honest academic solver. They just want to solve your problem. They have a few parameters which may or may not help. I don’t find it useful to introspect why the solver didn’t do the textbook algorithm.

3

Dualizing is sometimes beneficial for performance, the automatic setting of PreDual will automatically choose based on problem structure, you can try setting it to 0 to see if this helps.

Also, it says it in the log:

Extra simplex iterations from dual to original model: 1713
4

Thanks, I’ll try that parameter later.

But I don’t quite get what does “dualization” mean? In standard LP formula, the problem is determined by input data c::Vector, A::Matrix, b::Vector completely. So the data is already there—dualization won’t bring any new data.

If the solver thinks primal simplex algorithm is easier, then it perform calculations based on c, A, b. If the solver thinks dual simplex algorithm is easier, then it can also perform calculations based on c, A, b. So what does “pre-dualization” mean? Does it suggest additional memory allocation? What is the purpose then? Why is that necessary?

5

I assume presolve does different reductions depending on whether it is given the primal or the dual.

6

Yes, this might be the cause.

But theoretically speaking, the basic idea underpinning the primal simplex algorithm and the dual simplex algorithm should be the same. In my knowledge, the primal-side problem is a convex combination of columns, while the dual-side problem is a cutting plane problem. They both depends on a series of basis selections (i.e. some columns of A). Only the iteration path is different—the primal simplex maintains primal feasibility (i.e. x .>= 0) while the dual simplex maintains dual feasibility (i.e. reduced cost r .>= 0).

But there are indeed a lot of engineering factors that are hard to imagine unless one really tries to carry out an implementation.