Estimating solution time

[Jan Meese]

Is there a possibility to estimate the time the solver needs to solve the problem?
I am using MOSEK to solve a huge MILP, until now it takes hours and the REL_GAP is only at 13.32%.
Can the output produced by MOSEK get me a hint of how long it will take to solve the problem (e.g. does it take hours, days or years...?).

This is the output of MOSEK:

MOSEK Version 8.0.0.73 (Build date: 2017-5-5 15:43:04)
Copyright (c) MOSEK ApS, Denmark. WWW: mosek.com
Platform: Windows/64-X86

Problem
  Name                   :                
  Objective sense        : min            
  Type                   : LO (linear optimization problem)
  Constraints            : 51133213        
  Cones                  : 0              
  Scalar variables       : 15978241        
  Matrix variables       : 0              
  Integer variables      : 9583440        

Optimizer started.
Mixed integer optimizer started.
Threads used: 32
Presolve started.
Presolve terminated. Time = 1540.56
Presolved problem: 22873 variables, 45313 constraints, 112045 non-zeros
Presolved problem: 0 general integer, 14112 binary, 8761 continuous
Clique table size: 20263
BRANCHES RELAXS   ACT_NDS  DEPTH    BEST_INT_OBJ         BEST_RELAX_OBJ       REL_GAP(%)  TIME  
0        1        0        0        NA                   7.4991116667e+004    NA          1638.3
0        1        0        0        1.3761533000e+005    7.4991116667e+004    45.51       1656.1
0        1        0        0        8.8707050000e+004    7.4991116667e+004    15.46       1922.0
Cut generation started.
0        2        0        0        8.8707050000e+004    7.4991116667e+004    15.46       2018.1
Cut generation terminated. Time = 25.77
15       18       1        0        8.8707050000e+004    7.4991116667e+004    15.46       2396.6
28       31       1        0        8.8707050000e+004    7.4991116667e+004    15.46       2592.7
55       58       1        0        8.8707050000e+004    7.4991116667e+004    15.46       2617.7
83       86       1        0        8.8707050000e+004    7.4991116667e+004    15.46       2632.0
95       98       1        0        8.8707050000e+004    7.4991116667e+004    15.46       3285.3
157      160      1        0        8.8707050000e+004    7.4991116667e+004    15.46       3302.2
251      254      1        0        8.8707050000e+004    7.4991116667e+004    15.46       3314.4
424      427      1        0        8.8707050000e+004    7.4991116667e+004    15.46       3339.0

[removed a lot of lines...]

80470    71136    41852    322      8.6518625000e+004    7.4991116667e+004    13.32       24824.5
80587    71264    41935    278      8.6518625000e+004    7.4991116667e+004    13.32       24856.3
80659    71356    41999    323      8.6518625000e+004    7.4991116667e+004    13.32       24886.2

[Johan Löfberg]

All you can compute is an upper bound.

The number of AOU this will take, assuming you have a computer which can solve some 1 billion LPs per second, is 2^(9583440)/(1e9*3600*24*365*14.5e9) which is around 2^(10^7). Anything faster is a nice bonus, but unpredictable in theory

[Jan Meese]

AOU... a nice way of saying "it will propably take too much time"... :)

[Johan Löfberg]

No, it will probably terminate much faster than that, most likely within a fraction of a universe ages, but it is typically impossilbe to predict unless you've solved many similar problems before

[Erling D. Andersen]

Anyone working on MIP will say your problem is HUGE. And no one can say how long time it will take to solve.

As the MOSEK vendor I think MOSEK is fantastic of course but particularly for MIPs sometimes due to pure luck of course other optimizers can be faster.

If your problem is not secret then I suggest donating it at

   https://miplibsubmissions.zib.de

to research.

[Erling D. Andersen]

Btw 

   Presolved problem: 22873 variables, 45313 constraints, 112045 non-zeros

indicates  your formulation is a bit inefficient. 

[Johan Löfberg]

It is very common that YALMIP introduces auxiliary effectively redundant variables and constraints in order to simplify modelling, assuming most will be presolved by the solver and/or that they are so simple and sparse that it doesn't make any significant difference