R API slower than AMPL?
回答済み
I am making a comparison between solving a problem with Gurobi using AMPL and using directly the R API. The result I find is surprising, it is much faster to solve with AMPL (computing only solver times, without counting the rest of the R code). It is a small problem, a TSP problem with 35 cities, with iterative constraint addition for subtour elimination, with an average of about 400 calls to the solver (add constraints and call back). I have free academic license for both (AMPL(IDE) and GUROBI). What explanation can this have?
Thanks
-
Hi Manuel,
How are you implementing the iterative constraint addition in R? Gurobi's R interface does not support callbacks which is the standard way of realizing this approach.
You may want to compare the respective log files to see where the two runs differ.
Cheers,
Matthias0 -
Hi,
something like that
result <- gurobi(model, params)
time=result$runtime
while(#----subtour found--------){
# re = new subtour elimination constraint
model$A=rbind(model$A,re)
model$sense=c(model$sense,'>')
model$rhs=c(model$rhs,1)
result <- gurobi(model, params)
time=time+result$runtime
}thanks Matthias,
0 -
Hi Manuel,
yes, in this case, it is not too surprising that the R version is considerably slower. You are solving a new model from scratch in every iteration of that loop.
You should check out our object-oriented APIs like Python, to implement this more efficiently using callbacks: tsp.py
Cheers,
Matthias0 -
Hi Matthias,
But AMPL version also solves a new model in every iteration:
repeat while (STOP = 0) {
# Solve the problema
solve TSP_incremental;
# Updating solving tottime
let tottime := tottime+_solve_elapsed_time;
let subtours := subtours + 1;
# find the successors of each vertex
for {i in 1..n} {
let successorvertex[i] := sum{j in 1..n: j != i} j * x[member(i,CITIES),member(j,CITIES)];
}
# find a subtour
let currentvertex := 1;
let S[subtours] := {};
repeat {
let S[subtours] := S[subtours] union {currentvertex};
let currentvertex := successorvertex[currentvertex];
} until (currentvertex = 1);
# We check whether or not we have found a proper subtour
if (card(S[subtours]) >= n) then {
# Hamiltonian tour, terminate
let STOP := 1;
}
}Thanks
Cheeres
Manuel0 -
Not necessarily. While I cannot see where or how the new constraints are added to the model, it may very well be that you are updating an existing model and that Gurobi is not starting from scratch every time. As I said, the logs from both runs should tell you whether a new optimization has been started or whether an existing model is being re-optimized.
In any case, we recommend using one of the object-oriented APIs for such applications.
Cheers,
Matthias0 -
Thanks a lot, Matthias
Cheers,
Manuel
0 -
Hi
Log file extract (1 iteration)
R API
Gurobi 9.5.1 (linux64, R) logging started Xov 14 Abr 2022 17:49:02
Set parameter Username
Set parameter LogFile to value "TSP.log"
Academic license - for non-commercial use only - expires 2022-06-04
Gurobi Optimizer version 9.5.1 build v9.5.1rc2 (linux64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 82 rows, 1190 columns and 4932 nonzeros
Model fingerprint: 0xb304e278
Variable types: 0 continuous, 1190 integer (1190 binary)AMPL
Gurobi 9.5.0: Set parameter Username
presolve=0
timelim=3600
bestbound=1
outlev=1
Set parameter OutputFlag to value 1
Set parameter InfUnbdInfo to value 1
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 71 rows, 1190 columns and 2446 nonzeros
Model fingerprint: 0x2603310b
Variable types: 0 continuous, 1190 integer (1190 binary)both do the same thing, don't they?
Thanks!
Cheers
Manuel0 -
Hi Manuel,
Apparently, you are solving two very different models. The AMPL model has 71 constraints while the R model has 82 constraints and more than twice the number of nonzeros.
Additionally, you are using two different Gurobi versions (9.5.0 and 9.5.1).
Cheers,
Matthias0 -
Sorry Matthias, It's the same problem, log files extracts are from different iterations.
Here is the first iteration in bothAMPLPresolve eliminates 0 constraints and 68 variables.
Adjusted problem:
1190 variables, all binary
70 constraints, all linear; 2380 nonzeros
70 equality constraints
1 linear objective; 1190 nonzeros.
Gurobi 9.5.0: Set parameter Username
presolve=0
timelim=3600
bestbound=1
outlev=1
timing=1
Set parameter OutputFlag to value 1
Set parameter InfUnbdInfo to value 1
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 70 rows, 1190 columns and 2380 nonzeros
Model fingerprint: 0x651ffced
Variable types: 0 continuous, 1190 integer (1190 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [9e+00, 1e+02]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+00]
Found heuristic solution: objective 1896.6790000
Variable types: 0 continuous, 1190 integer (1190 binary)
Root relaxation: objective 6.382270e+02, 55 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 0 638.2270000 638.22700 0.00% - 0s
Explored 1 nodes (55 simplex iterations) in 0.00 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)
Solution count 2: 638.227 1896.68
Optimal solution found (tolerance 1.00e-04)
Best objective 6.382270000000e+02, best bound 6.382270000000e+02, gap 0.0000%
Set parameter Method to value 1R APIGurobi 9.5.1 (linux64, R) logging started Xov 14 Abr 2022 17:49:01
Set parameter Username
Set parameter LogFile to value "TSP.log"
Academic license - for non-commercial use only - expires 2022-06-04
Gurobi Optimizer version 9.5.1 build v9.5.1rc2 (linux64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 70 rows, 1190 columns and 2380 nonzeros
Model fingerprint: 0x1b8f1b5b
Variable types: 0 continuous, 1190 integer (1190 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [9e+00, 1e+02]
Bounds range [0e+00, 0e+00]
RHS range [1e+00, 1e+00]
Found heuristic solution: objective 1896.6790000
Presolve time: 0.01s
Presolved: 70 rows, 1190 columns, 2380 nonzeros
Variable types: 0 continuous, 1190 integer (1190 binary)
Root relaxation: objective 6.382270e+02, 55 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 0 638.2270000 638.22700 0.00% - 0s
Explored 1 nodes (55 simplex iterations) in 0.01 seconds (0.01 work units)
Thread count was 8 (of 8 available processors)
Solution count 2: 638.227 1896.68
Optimal solution found (tolerance 1.00e-04)
Best objective 6.382270000000e+02, best bound 6.382270000000e+02, gap 0.0000%CheersManuel0 -
Hi Manuel,
I don't see the issue - the logs are showing identical behavior even down to the number of simplex iterations required to reach optimality.
You may get different results in later iterations because your are solving the new model from scratch in R also including Presolving, while AMPL may just modify the existing formulation and does not apply a fresh round of presolving but can benefit from warmstarting information.
Please try comparing your code with our TSP example that I linked above.
Cheers,
Matthias0 -
Thanks Matthias,
R API interacts with Gurobi with files or by memory?
Cheers
Manuel
0 -
Hi Manuel,
The R API is passing data directly to Gurobi's C API:
No intermediate files will be created to pass the data.
Cheers,
Matthias0 -
Gurobi's presolve was being turned off when called from AMPL, but was on when called from the R API. This can be seen from the option presolve=0 echoed in the AMPL listing, and the presence of these lines only in the R listing:
Presolve time: 0.01s
Presolved: 70 rows, 1190 columns, 2380 nonzerosThe benefits of presolve for this model were minimal. The difference of 0.01 seconds seems insignificant, but Manuel was executing hundreds of solves in a loop, some of them taking 0.20 seconds or more in presolve, and apparently those fractions of seconds added up.
Manuel recently showed me the results of 95 tests with hundreds of solves each. When Gurobi's presolve was turned off in the R API runs, then they were a little faster than the AMPL runs -- typical 3-7% for the longer ones.
1 -
Thanks for the additional information, Robert!
I also noticed the different parameters being used in AMPL but wanted to make sure that at least the model that is being solved is identical for both approaches.
I still don't get the issue here, though - if there even is one. Presolve does not appear to change the problem in any kind or form and the solver seems to behave identically in both scenarios. So, turning tit off should only avoid a tiny bit of overhead in running the presolving routines once without performing any changes to the model. The slight difference of observed timings is most likely due to how AMPL and R interact with Gurobi. We typically recommend using one of our object-oriented APIs (not R nor Matlab) to have more control over the solver and to get the best performance.
Cheers,
Matthias0 -
Hi,
The problem is that in this type of model the presolve slows down the solution of the problem. I ran the AMPL version with presolve off, but the R API version with presolve on. That's why I got much worse times. When I turn presolve off in both cases, the times are slightly better in the R API version. Conclusion, in this kind of problems presolve should be disabled for better performance.
Cheers
Manuel
0
サインインしてコメントを残してください。
コメント
15件のコメント