Skip to main content

Extra variables being generate during solution process and IntInf has way higher value than the number of integer constraints I have in the model.

Answered

Comments

19 comments

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    The number of Integer Infeasibilities also reflects the number of violated bilinear terms in the associated linear relaxation. You have 706 binary variables + 139904 bilinear constraints (= 139904 bilinear terms).

    Best regards, 
    Jaromił

    0
  • Gaurav Malik
    Conversationalist
    First Question

    Hello Jaromil,
    Thanks for your reply! 
    Actually that is not completely true. I do not have any bilinear constraints. I do have some bilinear terms in the objective function but even when I remove those terms IntInf still stays 65k+. Can there be any other reason?

    However, these do vanish if I set Obj = 0. But I still have some extra variables i.e., 1074 + 1072 = 2146 expected. 1667 + 707 = 2374 seen after presolve. See image:

    1
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Gaurav,

    In your first screenshot you can see the line

    Presolved model has 139904 bilinear constraints.

    So Gurobi's presolve generated 139904 from your original model. These can all be violated in a linear relaxation and ultimately count into the IntInf number.

    In the new screenshot I do not see any larger IntInf than 78. Could you please clarify?

    Best regards, 
    Jaromił

    0
  • Gaurav Malik
    Conversationalist
    First Question

    That's exactly what's baffling me. The only difference between the two screenshots is that in the second screenshot case, my Obj = 0*Obj_original. 

     

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    That's exactly what's baffling me. The only difference between the two screenshots is that in the second screenshot case, my Obj = 0*Obj_original. 

    In your first screenshot, you can see

    Model has 140976 quadratic objective terms

    Because your objective is determined to be non-convex, Gurobi's presolve turns it into 1072 quadratic constraints and 139904 bilinear constraints.

    Best regards, 
    Jaromił

    0
  • Gaurav Malik
    Conversationalist
    First Question

    Thanks Jaromil!
    That makes perfect sense. Does this mean that such a model in practically unsolvable because of this extremely high number of auxiliary constraints and variables? Or is there still a hope?
    For a small subset of the cases, my obj can be convex but it will remain non-convex due to bilinear terms for most cases. Is there a way to formulate it better?

    P.S. I have set NonConvex parameter to 2 and DualReductions to 0. It helped in cases with 43+40 variables in the past. 

     

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Does this mean that such a model in practically unsolvable because of this extremely high number of auxiliary constraints and variables? Or is there still a hope?
    For a small subset of the cases, my obj can be convex but it will remain non-convex due to bilinear terms for most cases. Is there a way to formulate it better?

    I don't think you have to give up yet. You could first try to improve the coefficient ranges of your model.

    You can see that the coefficient ranges of your model are

    Matrix range     [8e-06, 1e+04]
    Objective range [1e-04, 3e-01]
    QObjective range [4e-08, 1e-01]
    Bounds range [1e-04, 1e+01]
    RHS range [1e-05, 1e+04]

    So there is a more than 6 orders of magnitude difference between the smallest and the biggest coefficient. Maybe re-scaling your model might already give it a needed performance boost, see our Guidelines for Numerical Issues for more information.

    The objective function is very dense. If possible, you could try to use some model knowledge and remove some bilinear terms from the objective, e.g., if you know that some product \(x \cdot y \) does not have any impact on the optimal solution point.

    You could experiment with the NoRelHeurTime parameter to run the No Relaxation heuristic which will try to find a feasible solution point before solving the root node relaxation.

    Best regards, 
    Jaromił

    0
  • Gaurav Malik
    Conversationalist
    First Question

    Thanks Jaromil!
    For the coefficient ranges, I did try to re-scale the model to have all the ranges between 1e-4 and 1e+4 e.g., I needed to multiply my objective function (was already in 500k Euros scale) by 10 but such things only increased the computation time. E.g., the computation time with Obj=0 increased from 40 seconds to 450 seconds. 


    Another important question about objective formulation. Does Gurobi with (NonConvex parameter = 2) consider the following terms also as bilinear terms:

    1.  variable1*variable1
    2. 0*variable1*variable2
    3. 0*variable1*MLinExpr[1]

    I have many terms with a 0 multiplier in the objective function. Do you think that using a for loop with an if coefficient>0 condition to form objective element wise would reduce these bilinear terms/constraints as compared to doing [Coeff. vector]*MVars*MLinkExpr?

    Additionally, is there a way to check/confirm the convexity of an objective function within Gurobi by using a function or attribute?

    Regards

    Gaurav

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Gaurav,

    For the coefficient ranges, I did try to re-scale the model to have all the ranges between 1e-4 and 1e+4 e.g., I needed to multiply my objective function (was already in 500k Euros scale) by 10 but such things only increased the computation time. E.g., the computation time with Obj=0 increased from 40 seconds to 450 seconds.

    Did you also check the quality of the solution point. It may be that the badly scaled model converges faster, but that it also returns a qualitatively worse solution, e.g., larger constraint violations.

    Does Gurobi with (NonConvex parameter = 2) consider the following terms also as bilinear terms:

    1.  variable1*variable1
    2. 0*variable1*variable2
    3. 0*variable1*MLinExpr[1]
    1. Yes
    2. Yes, but it will be automatically removed
    3. Yes, but it will be automatically removed

    In general, if you know that a coefficient is 0 then I would not add such a term to the model.

    Do you think that using a for loop with an if coefficient>0 condition to form objective element wise would reduce these bilinear terms/constraints as compared to doing [Coeff.vector]*MVars*MLinkExpr?

    It should make no difference because the terms with a 0 coefficient will be removed anyway. However, you might consider removing all terms with, e.g., a coefficient with ABS(coef) <= 1e-7.

    Additionally, is there a way to check/confirm the convexity of an objective function within Gurobi by using a function or attribute?

    If you set the parameter NonConvex=1 then Gurobi will only solve your model if it is able to reformulate is into a convex model in presolve. Otherwise, it will throw an error. If you set the parameter NonConvex=0 then Gurobi will only solve your model if the original model, i.e., the un-presolved model, is determined to be convex. Otherwise, an error is thrown.

    Please note that it is possible that your model is indeed convex but Gurobi is not able to detect it.

    Best regards, 
    Jaromił

    0
  • Gaurav Malik
    Conversationalist
    First Question

    "However, you might consider removing all terms with, e.g., a coefficient with ABS(coef) <= 1e-7"

    Thanks. This is a good suggestion. Is there a straightforward way to do this for a non-convex quadratic obj function?

    Regards

    Gaurav

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Is there a straightforward way to do this for a non-convex quadratic obj function?

    After you have constructed your objective, you first call the update method to push all changes into the model.

    You then retrieve the objective via the getObjective method. This should give you a QuadExpr object. Because your model is quadratic, you will have to rebuild it. This means that you have to go over all entries in your objective and construct a new one. This can be done as follows

    obj = m.getObjective() # objective is quadratic so you will get a QuadExpr object
    linobjpart = obj.getLinExpr() # retrieve linear part of quadratic objective
    newobj = gp.QuadExpr(0)

    # manage linear part first
    for i in range(linobjpart.size()):
    coef = linobjpart.getCoef(i)
    var = linobjpart.getVar(i)
    if abs(coef) > 1e-7:
    newobj.add(coef * var)

    # manage quadratic part second
    for i in range(obj.size()):
    coef = obj.getCoef(i)
    var1 = obj.getVar1(i)
    var2 = obj.getVar2(i)
    if abs(coef) > 1e-7:
    newobj.add(coef * var1 * var2)

    m.setObjective(newobj)

    Please note that I did not test the code.

    Best regards, 
    Jaromił

     

    0
  • Gaurav Malik
    Conversationalist
    First Question

    Hi Jaromil!

    Thanks for this suggestion. I actually used the limit of 1e-3 and this way I could reduce the size of my Obj from 280k to 12k. This of course has implications for the optimality. I am currently accessing the solutions (if obtainable) with this workaround. 

    In the meantime, another way to reduce the size of the Objective function is by adding extra variables. This is sort of cheating but just wanted to know if it makes any difference? e.g., 


    add variable X1

    add variable X2
    F = X1+X2

    optimise F 

    Obj has a size of 2 in this case whereas if 

    add variable X1

    add variable X2

    add variable F

    add constraint F-X1+X2>=1e-5

    add constraint F-X1+X2<=1e-5

    optimise F

    Here the Obj will have a size of 1 but of course we have extra constraints. 

    Do you think the latter can have positive effects in terms of the solution process? In this way I can reduce Obj size from 280K to 5k but will need to add about 5k extra linear constraints as well.

    Regards

    Gaurav 

     

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Gaurav,

    Do you think the latter can have positive effects in terms of the solution process? In this way I can reduce Obj size from 280K to 5k but will need to add about 5k extra linear constraints as well.

    This should normally have no effect on the performance, because you just move the nonzeros from the objective to constraints. However, it may be worth a try, especially if you can provide some tight bounds for auxiliary variables, which you might obtain through some application knowledge.

    Best regards, 
    Jaromił

    0
  • Gaurav Malik
    Conversationalist
    First Question

    Hello Jaromil, 

    Indeed, it did not make an appreciable difference. 

    I have been able to solve feasibility problem with Obj = 0 within 40-60 seconds, the problem with an irrelevant linear obj function e.g., Obj = X.sum() within 1000-1200 seconds. However, the problem with my desired Objective function which is non-convex quadratic remains unsolved even after running for more than 24 hours (even after filtering for terms with coefficient>1e-3). 
    Can you kindly suggest certain reformulation tips to make the problem solve within appreciable time?
    Do you think that it is normal that it the solution time scales like that? Is it just the supposed computation time or is it running into numerical issues? I am willing to wait out if it can be expected to converge after a certain amount of time but at the moment it just seems like it will never be solved. 

    The following is the log file before I stopped the solver manually

    Gurobi 10.0.0 (win64) logging started Sat Nov 11 14:02:12 2023

    Set parameter LogFile to value "gurobi_cs3.log"
    Discarded solution information

    Gurobi 10.0.0 (win64) logging started Sat Nov 11 14:02:35 2023

    Set parameter LogFile to value "gurobi_cs3.log"
    Discarded solution information
    Gurobi Optimizer version 10.0.0 build v10.0.0rc2 (win64)

    CPU model: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz, instruction set [SSE2|AVX|AVX2]
    Thread count: 6 physical cores, 12 logical processors, using up to 12 threads

    Optimize a model with 6324 rows, 2998 columns and 47220 nonzeros
    Model fingerprint: 0xd633f72c
    Model has 2628 quadratic objective terms
    Variable types: 1926 continuous, 1072 integer (1072 binary)
    Coefficient statistics:
      Matrix range     [9e-06, 1e+04]
      Objective range  [2e-03, 3e+02]
      QObjective range [4e-02, 1e+02]
      Bounds range     [1e-04, 1e+01]
      RHS range        [1e-03, 1e+04]
    Presolve removed 2457 rows and 738 columns
    Presolve time: 0.24s
    Presolved: 6980 rows, 4893 columns, 44456 nonzeros
    Presolved model has 1072 quadratic constraint(s)
    Presolved model has 1556 bilinear constraint(s)
    Variable types: 4357 continuous, 536 integer (536 binary)
    Starting NoRel heuristic
    Found phase-1 solution: relaxation 4.07079e+07
    Found phase-1 solution: relaxation 3.56754e+07
    Found phase-1 solution: relaxation 2.84033e+07
    Found phase-1 solution: relaxation 2.80211e+07
    Found phase-1 solution: relaxation 2.66263e+07
    Found phase-1 solution: relaxation 2.38315e+07
    Found phase-1 solution: relaxation 2.09587e+07
    Found phase-1 solution: relaxation 2.00396e+07
    Found phase-1 solution: relaxation 1.17767e+07
    Found phase-1 solution: relaxation 1.14465e+07
    Found phase-1 solution: relaxation 1.14434e+07
    Found phase-1 solution: relaxation 1.02798e+07
    Elapsed time for NoRel heuristic: 5s (best bound -721945)
    Found phase-1 solution: relaxation 1.02787e+07
    Found phase-1 solution: relaxation 1.01797e+07
    Found phase-1 solution: relaxation 9.82707e+06
    Found phase-1 solution: relaxation 9.51547e+06
    Found phase-1 solution: relaxation 8.39308e+06
    Found phase-1 solution: relaxation 8.39202e+06
    Found phase-1 solution: relaxation 8.031e+06
    Found phase-1 solution: relaxation 7.88233e+06
    Found phase-1 solution: relaxation 7.74096e+06
    Found phase-1 solution: relaxation 7.66319e+06
    Found phase-1 solution: relaxation 7.07854e+06
    Found phase-1 solution: relaxation 6.47003e+06
    Found phase-1 solution: relaxation 5.61754e+06
    Elapsed time for NoRel heuristic: 10s (best bound -721945)
    Found phase-1 solution: relaxation 4.36451e+06
    Found phase-1 solution: relaxation 4.10951e+06
    Found phase-1 solution: relaxation 3.32296e+06
    Elapsed time for NoRel heuristic: 17s (best bound -721945)
    Found phase-1 solution: relaxation 2.97953e+06
    Found phase-1 solution: relaxation 2.18814e+06
    Found phase-1 solution: relaxation 2.18814e+06
    Found phase-1 solution: relaxation 2.03947e+06
    Found phase-1 solution: relaxation 1.76662e+06
    Found phase-1 solution: relaxation 1.74283e+06
    Elapsed time for NoRel heuristic: 22s (best bound -721945)
    Found phase-1 solution: relaxation 1.61456e+06
    Found phase-1 solution: relaxation 1.60965e+06
    Found phase-1 solution: relaxation 1.6095e+06
    Found phase-1 solution: relaxation 1.42623e+06
    Found phase-1 solution: relaxation 1.42426e+06
    Elapsed time for NoRel heuristic: 28s (best bound -721945)
    Found phase-1 solution: relaxation 1.41686e+06
    Found phase-1 solution: relaxation 1.41667e+06
    Found phase-1 solution: relaxation 690927
    Elapsed time for NoRel heuristic: 33s (best bound -721945)
    Found phase-1 solution: relaxation 661143
    Found phase-1 solution: relaxation 656666
    Found phase-1 solution: relaxation 655889
    Found phase-1 solution: relaxation 655090
    Found phase-1 solution: relaxation 655017
    Found phase-1 solution: relaxation 624054
    Elapsed time for NoRel heuristic: 38s (best bound -721945)
    Found phase-1 solution: relaxation 387158
    Found phase-1 solution: relaxation 4819.57
    Found phase-1 solution: relaxation 4776.55
    Found phase-1 solution: relaxation 4760.52
    Elapsed time for NoRel heuristic: 44s (best bound -721945)
    Found phase-1 solution: relaxation 4163.94
    Found phase-1 solution: relaxation 4163.94
    Found phase-1 solution: relaxation 4159.76
    Elapsed time for NoRel heuristic: 52s (best bound -721945)
    Found phase-1 solution: relaxation 2939.08
    Found phase-1 solution: relaxation 2919.28
    Found phase-1 solution: relaxation 2892.49
    Elapsed time for NoRel heuristic: 58s (best bound -721945)
    Found phase-1 solution: relaxation 2879.1
    Found phase-1 solution: relaxation 2875.91
    Found phase-1 solution: relaxation 2863.62
    Found phase-1 solution: relaxation 2201.91
    Elapsed time for NoRel heuristic: 64s (best bound -721945)
    Found phase-1 solution: relaxation 2197.4
    Found phase-1 solution: relaxation 2188.97
    Found phase-1 solution: relaxation 1592.42
    Found phase-1 solution: relaxation 1590.7
    Found phase-1 solution: relaxation 1590.04
    Found phase-1 solution: relaxation 1588.81
    Found phase-1 solution: relaxation 1588.07
    Elapsed time for NoRel heuristic: 70s (best bound -721945)
    Found phase-1 solution: relaxation 1587.66
    Found phase-1 solution: relaxation 195.106
    Elapsed time for NoRel heuristic: 76s (best bound -721945)
    Found phase-1 solution: relaxation 194.571
    Found phase-1 solution: relaxation 181.834
    Found phase-1 solution: relaxation 181.639
    Elapsed time for NoRel heuristic: 83s (best bound -721945)
    Found phase-1 solution: relaxation 180.364
    Found phase-1 solution: relaxation 151.247
    Found phase-1 solution: relaxation 128.011
    Found phase-1 solution: relaxation 97.7612
    Elapsed time for NoRel heuristic: 91s (best bound -721945)
    Found phase-1 solution: relaxation 63.0452
    Found phase-1 solution: relaxation 43.6743
    Found phase-1 solution: relaxation 43.6632
    Found phase-1 solution: relaxation 43.6375
    Found phase-1 solution: relaxation 43.3979
    Elapsed time for NoRel heuristic: 97s (best bound -721945)
    Found phase-1 solution: relaxation 40.3222
    Elapsed time for NoRel heuristic: 102s (best bound -721945)
    Found phase-1 solution: relaxation 19.2267
    Found phase-1 solution: relaxation 19.2009
    Found phase-1 solution: relaxation 18.3264
    Elapsed time for NoRel heuristic: 108s (best bound -721945)
    Found phase-1 solution: relaxation 0.253805
    Found phase-1 solution: relaxation 0.253678
    Found phase-1 solution: relaxation 0.235663
    Elapsed time for NoRel heuristic: 117s (best bound -721945)
    Elapsed time for NoRel heuristic: 122s (best bound -721945)
    Elapsed time for NoRel heuristic: 128s (best bound -721945)
    Found phase-1 solution: relaxation 0
    Found heuristic solution: objective -360916.7779
    Transition to phase 2
    Elapsed time for NoRel heuristic: 143s (best bound -721945)
    Found heuristic solution: objective -360916.7781
    Found heuristic solution: objective -360916.7798
    Elapsed time for NoRel heuristic: 148s (best bound -721945)
    Elapsed time for NoRel heuristic: 189s (best bound -721945)
    Elapsed time for NoRel heuristic: 197s (best bound -721945)
    Warning: Markowitz tolerance tightened to 0.5

    Root simplex log...

    Iteration    Objective       Primal Inf.    Dual Inf.      Time
           0   -5.4845137e+16   7.415648e+16   0.000000e+00    198s
        6393   -7.2194456e+05   0.000000e+00   0.000000e+00    199s

    Root relaxation: objective -7.219446e+05, 6393 iterations, 0.93 seconds (1.20 work units)

        Nodes    |    Current Node    |     Objective Bounds      |     Work
     Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

         0     0 -721944.56    0 1172 -360916.78 -721944.56   100%     -  198s
         0     0 -721934.25    0 1172 -360916.78 -721934.25   100%     -  198s
    H    0     0                    -360916.7798 -721934.25   100%     -  198s
    H    0     0                    -360916.7952 -488154.40  35.3%     -  200s
         0     0 -488154.40    0 1178 -360916.80 -488154.40  35.3%     -  200s
         0     0 -486531.81    0 1172 -360916.80 -486531.81  34.8%     -  200s
         0     0 -457807.83    0 1202 -360916.80 -457807.83  26.8%     -  201s
         0     0 -457639.23    0 1197 -360916.80 -457639.23  26.8%     -  201s
         0     0 -415879.51    0 1167 -360916.80 -415879.51  15.2%     -  206s
         0     0 -415878.11    0 1170 -360916.80 -415878.11  15.2%     -  206s
         0     0 -412894.97    0 1173 -360916.80 -412894.97  14.4%     -  207s
         0     0 -385211.31    0 1141 -360916.80 -385211.31  6.73%     -  211s
         0     0 -384748.92    0 1145 -360916.80 -384748.92  6.60%     -  211s
         0     0 -383920.18    0 1141 -360916.80 -383920.18  6.37%     -  212s
         0     0 -383041.59    0 1132 -360916.80 -383041.59  6.13%     -  212s
         0     0 -378659.52    0 1133 -360916.80 -378659.52  4.92%     -  214s
         0     0 -378086.88    0 1133 -360916.80 -378086.88  4.76%     -  215s
         0     0 -374733.03    0 1096 -360916.80 -374733.03  3.83%     -  216s
         0     0 -374510.93    0 1089 -360916.80 -374510.93  3.77%     -  217s
         0     0 -373093.48    0 1063 -360916.80 -373093.48  3.37%     -  218s
         0     0 -372987.78    0 1062 -360916.80 -372987.78  3.34%     -  218s
         0     0 -372968.02    0 1072 -360916.80 -372968.02  3.34%     -  218s
         0     0 -372956.51    0 1063 -360916.80 -372956.51  3.34%     -  218s
         0     0 -372951.08    0 1064 -360916.80 -372951.08  3.33%     -  218s
         0     0 -372948.30    0 1064 -360916.80 -372948.30  3.33%     -  219s
         0     0 -372948.28    0 1065 -360916.80 -372948.28  3.33%     -  219s
         0     0 -372948.27    0 1065 -360916.80 -372948.27  3.33%     -  219s
         0     0 -372946.51    0 1059 -360916.80 -372946.51  3.33%     -  222s
         0     2 -372946.50    0 1059 -360916.80 -372946.50  3.33%     -  223s
         7    12  postponed    3      -360916.80 -372087.05  3.09%  7802  268s
        13    18  postponed    4      -360916.80 -371898.62  3.04% 11233  296s
        19    24  postponed    4      -360916.80 -371898.62  3.04%  9312  308s
        25    28 infeasible    5      -360916.80 -371898.62  3.04%  8842  337s
        31    34 infeasible    5      -360916.80 -371898.62  3.04%  8829  341s
        41    40 infeasible    5      -360916.80 -371379.79  2.90%  7235  349s
        51    47 -368274.15    5 1052 -360916.80 -371379.79  2.90%  6606  356s
        60    53 -368194.54    7 1049 -360916.80 -371379.79  2.90%  6368  392s
    H   71    54                    -360916.8140 -371379.79  2.90%  6895  407s
    H   81    54                    -360916.8158 -371379.79  2.90%  6508  407s
        87    64  postponed   11      -360916.82 -371379.79  2.90%  6263  419s
       101    69 infeasible   12      -360916.82 -371379.79  2.90%  5723  503s
       116    76 infeasible   10      -360916.82 -371379.79  2.90%  6040  534s
       128    84  postponed   10      -360916.82 -371379.79  2.90%  6231  550s
       143    97  postponed   11      -360916.82 -371379.79  2.90%  6229  557s
       158   100 infeasible   12      -360916.82 -371379.79  2.90%  6076  565s
       170   110 infeasible   12      -360916.82 -371379.79  2.90%  5956  642s
       187   118 -367693.83   12 1038 -360916.82 -371379.79  2.90%  6477  657s
       204   126 -366058.11   19  979 -360916.82 -371379.79  2.90%  6395  731s
       216   136 -365261.11   26  953 -360916.82 -371379.79  2.90%  6945  747s
       230   149 -364178.86   34  865 -360916.82 -371379.79  2.90%  7072  779s
    H  239   149                    -360916.9479 -371379.79  2.90%  7252  779s
       247   163  postponed   36      -360916.95 -371379.79  2.90%  7177  796s
       275   183  postponed   37      -360916.95 -371379.79  2.90%  6875  832s
       299   199  postponed   38      -360916.95 -371379.79  2.90%  6870  858s
       330   232 infeasible   39      -360916.95 -371379.79  2.90%  6535  876s
    H  334   232                    -360916.9489 -371379.79  2.90%  6457  876s
    H  344   232                    -360916.9498 -371379.79  2.90%  6365  876s
       378   251 -362753.68   42  799 -360916.95 -371379.79  2.90%  5924  898s
       409   252 -365779.30   21  305 -360916.95 -371379.79  2.90%  5725  972s
       411   253 -371379.79    5  288 -360916.95 -371379.79  2.90%  5697  978s
       412   254 -366503.18   19  243 -360916.95 -371379.79  2.90%  5683  980s
       437   271 -367642.78   18  225 -360916.95 -371379.79  2.90%  5358  986s
       444   278 -371379.79   18  951 -360916.95 -371379.79  2.90%  5304  997s
       449   282 -371379.79   19  948 -360916.95 -371379.79  2.90%  5277 1011s
       455   286 -371379.79   20  918 -360916.95 -371379.79  2.90%  5289 1019s
       461   287 -371379.79   20  933 -360916.95 -371379.79  2.90%  5302 1021s
       467   289 infeasible   21      -360916.95 -371379.79  2.90%  5264 1038s
       473   293 -371379.79   21  915 -360916.95 -371379.79  2.90%  5280 1043s
       481   293 -371379.79   22  912 -360916.95 -371379.79  2.90%  5252 1050s
       490   295  postponed   22      -360916.95 -371379.79  2.90%  5253 1057s
       498   297  postponed   23      -360916.95 -371379.79  2.90%  5239 1061s
    H  501   281                    -360916.9525 -371379.79  2.90%  5209 1061s
       508   281 infeasible   23      -360916.95 -371379.79  2.90%  5199 1067s
       518   277 infeasible   25      -360916.95 -371379.79  2.90%  5198 1070s
    H  540   256                    -360916.9528 -371379.79  2.90%  5140 1073s
       541   263  postponed   26      -360916.95 -371379.79  2.90%  5152 1082s
       550   263 infeasible   27      -360916.95 -371379.79  2.90%  5135 1085s
       566   266 infeasible   27      -360916.95 -371379.79  2.90%  5050 1091s
       576   274  postponed   23      -360916.95 -371379.79  2.90%  5047 1095s
       589   276  postponed   23      -360916.95 -371379.79  2.90%  5005 1108s
       607   278  postponed   24      -360916.95 -371379.79  2.90%  4941 1111s
    H  614   263                    -360916.9781 -371379.79  2.90%  4924 1111s
       617   270  postponed   24      -360916.98 -371379.79  2.90%  4917 1116s
       627   278  postponed   25      -360916.98 -371379.79  2.90%  4910 1122s
       639   286  postponed   25      -360916.98 -371379.79  2.90%  4898 1125s
    H  651   270                    -360916.9783 -371379.79  2.90%  4857 1125s
       653   286  postponed   26      -360916.98 -371379.79  2.90%  4862 1131s
       669   296  postponed   24      -360916.98 -371379.79  2.90%  4836 1136s
       685   303 infeasible   27      -360916.98 -371379.79  2.90%  4781 1142s
       695   300 -371379.79   66  648 -360916.98 -371379.79  2.90%  4783 1330s
       699   314  postponed   27      -360916.98 -371379.79  2.90%  4775 1336s
       715   330  postponed   26      -360916.98 -371379.79  2.90%  4755 1342s
       736   344  postponed   28      -360916.98 -371379.79  2.90%  4713 1350s
       758   357  postponed   26      -360916.98 -371379.79  2.90%  4673 1358s
       782   347  postponed   29      -360916.98 -371379.79  2.90%  4630 1368s
       798   347  postponed   28      -360916.98 -371379.79  2.90%  4633 1378s
    H  817   330                    -360916.9783 -371379.79  2.90%  4639 1378s
       820   335  postponed   29      -360916.98 -371379.79  2.90%  4646 1387s
       834   328  postponed   29      -360916.98 -371379.79  2.90%  4688 1397s
       858   318  postponed   30      -360916.98 -371379.79  2.90%  4711 1425s
       876   314 infeasible   31      -360916.98 -371379.79  2.90%  4828 1433s
       898   315  postponed   35      -360916.98 -371379.79  2.90%  4853 1442s
       910   323  postponed   36      -360916.98 -371379.79  2.90%  4923 1452s
       922   323  postponed   37      -360916.98 -371379.79  2.90%  5005 1473s
       948   327  postponed   50      -360916.98 -371379.79  2.90%  5075 1484s
       961   341  postponed   52      -360916.98 -371379.79  2.90%  5153 1497s
       979   352  postponed   55      -360916.98 -371379.79  2.90%  5259 1513s
      1000   361  postponed   58      -360916.98 -371379.79  2.90%  5360 1527s
      1022   355 infeasible   62      -360916.98 -371379.79  2.90%  5449 1556s
      1059   356  postponed   38      -360916.98 -371379.79  2.90%  5506 1575s
      1085   370  postponed   41      -360916.98 -371379.79  2.90%  5572 1592s
      1115   391  postponed   45      -360916.98 -371379.79  2.90%  5596 1611s
      1144   411  postponed   50      -360916.98 -371379.79  2.90%  5697 1632s
      1172   424  postponed   55      -360916.98 -371379.79  2.90%  5815 1656s
      1221   431  postponed   60      -360916.98 -371379.79  2.90%  5864 1679s
      1268   468  postponed   65      -360916.98 -371379.79  2.90%  5931 1706s
      1313   436 infeasible   72      -360916.98 -371379.79  2.90%  6035 1761s
      1428   461 infeasible   79      -360916.98 -371379.79  2.90%  5914 1789s
      1467   466 infeasible   57      -360916.98 -371379.79  2.90%  5989 1815s
      1538   494  postponed   57      -360916.98 -371379.79  2.90%  5976 1845s
      1582   531  postponed   61      -360916.98 -371379.79  2.90%  6092 1886s
      1639   560  postponed   71      -360916.98 -371379.79  2.90%  6229 1936s
      1734   556 infeasible   84      -360916.98 -371379.79  2.90%  6281 2017s
      1904   560  postponed  102      -360916.98 -371379.79  2.90%  6192 2071s
      2060   593  postponed  119      -360916.98 -371379.79  2.90%  6140 2125s
      2185   652 infeasible   62      -360916.98 -371379.79  2.90%  6180 2176s
      2270   653  postponed   71      -360916.98 -371379.79  2.90%  6272 2238s
      2445   713  postponed   41      -360916.98 -371379.79  2.90%  6198 2296s
      2547   713 infeasible   57      -360916.98 -371379.79  2.90%  6270 2373s
      2723   798  postponed   73      -360916.98 -371379.79  2.90%  6233 2450s
      2846   819  postponed   94      -360916.98 -371379.79  2.90%  6338 2540s
      3089   857  postponed   54      -360916.98 -371379.79  2.90%  6293 2604s
      3223   871 infeasible   75      -360916.98 -371379.79  2.90%  6329 2672s
      3401   913  postponed   87      -360916.98 -371379.79  2.90%  6287 2736s
      3549   958  postponed   44      -360916.98 -371379.79  2.90%  6306 2798s
      3698  1039  postponed   62      -360916.98 -371379.79  2.90%  6321 2866s
      3849  1127  postponed   74      -360916.98 -371379.79  2.90%  6341 2933s
      3977  1207  postponed   92      -360916.98 -371379.79  2.90%  6398 3003s
      4117  1276  postponed  111      -360916.98 -371379.79  2.90%  6444 3073s
      4238  1338  postponed  128      -360916.98 -371379.79  2.90%  6499 3148s
      4360  1401  postponed   66      -360916.98 -371379.79  2.90%  6558 3224s
      4521  1514  postponed   61      -360916.98 -371379.79  2.90%  6581 3303s
      4682  1626 infeasible   81      -360916.98 -371379.79  2.90%  6630 3386s
      4852  1743  postponed  104      -360916.98 -371379.79  2.90%  6679 3471s
      5021  1864  postponed  125      -360916.98 -371379.79  2.90%  6730 3557s
      5194  1982  postponed  145      -360916.98 -371379.79  2.90%  6779 3641s
      5374  2104  postponed  173      -360916.98 -371379.79  2.90%  6821 3732s
      5566  2244  postponed  197      -360916.98 -371379.79  2.90%  6855 3828s
      5752  2388  postponed  227      -360916.98 -371379.79  2.90%  6912 3937s
      5988  2514  postponed  260      -360916.98 -371379.79  2.90%  6946 4049s
      6246  2654  postponed  293      -360916.98 -371379.79  2.90%  6961 4169s
      6514  2798  postponed  323      -360916.98 -371379.79  2.90%  6968 4293s
      6750  2972  postponed  350      -360916.98 -371379.79  2.90%  7009 4418s
      7010  3149 infeasible  385      -360916.98 -371379.79  2.90%  7032 4546s
      7293  3290 infeasible  421      -360916.98 -371379.79  2.90%  7054 4677s
      7608  3451 infeasible  218      -360916.98 -371379.79  2.90%  7057 4809s
      7885  3599  postponed  263      -360916.98 -371379.79  2.90%  7092 4948s
      8179  3795  postponed  277      -360916.98 -371379.79  2.90%  7127 5095s
      8525  3865  postponed  297      -360916.98 -371379.79  2.90%  7145 5236s
      8879  3885  postponed  327      -360916.98 -371379.79  2.90%  7105 5373s
      9233  3904  postponed  347      -360916.98 -371379.79  2.90%  7036 5503s
      9590  3999  postponed  381      -360916.98 -371379.79  2.90%  6960 5656s
      9963  4089  postponed  673      -360916.98 -371379.79  2.90%  6925 5970s
     10781  4226 infeasible  345      -360916.98 -371379.79  2.90%  6812 6297s
     11526  4275 infeasible   37      -360916.98 -371379.79  2.90%  6748 6642s
     12431  4073 infeasible  400      -360916.98 -371379.79  2.90%  6632 6971s
     13389  3977 infeasible  480      -360916.98 -371379.79  2.90%  6439 7318s
     14245  3941 infeasible  350      -360916.98 -371379.79  2.90%  6315 7681s
     15093  3858 infeasible  548      -360916.98 -371379.79  2.90%  6223 8065s
     16038  3556 infeasible  419      -360916.98 -371379.79  2.90%  6118 8465s
     17176  3466 infeasible  227      -360916.98 -371379.79  2.90%  5956 8849s
     18218  3140 infeasible  187      -360916.98 -371379.79  2.90%  5862 9230s
     19574  2822 infeasible  336      -360916.98 -371379.79  2.90%  5714 9615s
     20830  2439 infeasible  218      -360916.98 -371379.79  2.90%  5606 10008s
     22199  1919 infeasible  224      -360916.98 -371379.79  2.90%  5494 10404s
     23781  1659 infeasible  176      -360916.98 -371379.79  2.90%  5353 10844s
     25311  1616  postponed   89      -360916.98 -371379.79  2.90%  5277 11334s
     26960   734  postponed  100      -360916.98 -371379.79  2.90%  5256 11756s
     29715   851  postponed   67      -360916.98 -371379.79  2.90%  4941 11879s
     29904   969  postponed   59      -360916.98 -371379.79  2.90%  4972 12023s
     30142  1066 infeasible   85      -360916.98 -371379.79  2.90%  5006 12201s
     30462  1258  postponed  119      -360916.98 -371379.79  2.90%  5040 12407s
     30791  1465  postponed  160      -360916.98 -371379.79  2.90%  5088 12680s
     31304  1720 infeasible  217      -360916.98 -371379.79  2.90%  5139 13044s
     31893  2091  postponed  288      -360916.98 -371379.79  2.90%  5211 13502s
     32848  2535  postponed  388      -360916.98 -371379.79  2.90%  5284 14041s
     33956  2434  postponed   82      -360916.98 -371379.79  2.90%  5371 14667s
     35629  2613 infeasible  252      -360916.98 -371379.79  2.90%  5378 15319s
     37278  3031  postponed   85      -360916.98 -371379.79  2.90%  5423 16008s
     38836  3422 infeasible  220      -360916.98 -371379.79  2.90%  5498 16750s
     40451  4034  postponed  289      -360916.98 -371379.79  2.90%  5575 17568s
     42041  4699  postponed  239      -360916.98 -371379.79  2.90%  5671 18417s
     43570  5312  postponed  329      -360916.98 -371379.79  2.90%  5774 19366s
     45187  6048  postponed  425      -360916.98 -371379.79  2.90%  5878 20382s
     47163  6450  postponed  529      -360916.98 -371379.79  2.90%  5965 21394s
     49571  7163  postponed  636      -360916.98 -371379.79  2.90%  6004 22430s
     51480  7628  postponed  742      -360916.98 -371379.79  2.90%  6086 23464s
     53831  8325 infeasible  612      -360916.98 -371379.79  2.90%  6130 24520s
     55982  8310  postponed  432      -360916.98 -371379.79  2.90%  6193 25600s
     58549  8458  postponed  191      -360916.98 -371379.79  2.90%  6182 26620s
     61001  8608  postponed  210      -360916.98 -371379.79  2.90%  6183 27701s
     63661  9037  postponed  335      -360916.98 -371379.79  2.90%  6179 28813s
     66050  9878 infeasible  513      -360916.98 -371379.79  2.90%  6209 30225s
     68989 10842  postponed  603      -360916.98 -371379.79  2.90%  6269 31672s
     71849 11661 infeasible  429      -360916.98 -371379.79  2.90%  6334 33092s
     74846 12841  postponed  577      -360916.98 -371379.79  2.90%  6382 34541s
     77880 13409  postponed  266      -360916.98 -371379.79  2.90%  6445 36153s
     82388 13987  postponed 1344      -360916.98 -371379.79  2.90%  6424 37675s
     86184 15397  postponed  628      -360916.98 -371379.79  2.90%  6419 39025s
     88280 16499  postponed  940      -360916.98 -371379.79  2.90%  6502 40367s
     91020 17617  postponed  265      -360916.98 -371379.79  2.90%  6556 41770s
     94040 18841  postponed  302      -360916.98 -371379.79  2.90%  6598 43336s
    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Can you kindly suggest certain reformulation tips to make the problem solve within appreciable time?

    For this you would have to share the model. Note that uploading files in the Community Forum is not possible but we discuss an alternative in Posting to the Community Forum.

    Do you think that it is normal that it the solution time scales like that?

    Yes, definitely. If your model has a lot of nonconvex terms then it is expected to take a possibly (extremely) long time to solve.

    Is it just the supposed computation time or is it running into numerical issues?

    From the logs, you can see that a lot of nodes have the "postponed" status. This only happens if the LP relaxations run into numerical issues.

    You could try using NodeMethod=2, Crossover=0, Method=0. This will lead to Gurobi using the Barrier method to solve each node relaxation. Maybe this performs a bit better.

    Anyway, you should try to re-scale your model as discussed in our Guidelines for Numerical Issues. This is the best way to avoid numerical trouble.

    Additionally, you could try updating to the latest version and/or wait until version 11 is released in December.

    Best regards, 
    Jaromił

    0
  • Gaurav Malik
    Conversationalist
    First Question

    Thanks Jaromił for the reply. 
    I am using a big M trick in my constraints so scaling differently is a bit tricky. I will try some things and get back to you. 

    About the parameters,

    NodeMethod=2, Crossover=0, Method=0. 
    "Note that barrier is not an option for MIQP node relaxations."

    Can I ignore this lines and use if for my nonconvex MIQP?

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Can I ignore this lines and use if for my nonconvex MIQP?

    Good point. No, unfortunately you cannot (unless you see some difference when you run with the parameters). Then I think the only way out is to re-scale or wait for the new release.

    0
  • Gaurav Malik
    Conversationalist
    First Question

    Hi Jaromił,

    Here you can find my python script and an excel dependency. 
    I would love to get some feedback on some tips on reformulating this model to avoid numerical issues. Thank you very much in advance! 

    Regards
    Gaurav

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Gaurav,

    I had a look at your model. I cannot think of any reformulation which might help here.

    However, you might want to try the following:

    For example, you have constraint (I generated the model using the write method to write an LP file)

    R848: - 5.208333333333334 C2282 - 5.208333333333334 C2424 - C2566 + C2992 = 0

    The value \(5.208333333333334\) is actually \( = \frac{125}{24}\). You could multiply the whole constraint by \(24\) to get a nice integer constraint

    R848: - 125 C2282 - 125  C2424 - 24 C2566 + 24 C2992 = 0

    From looking at your model, you can apply this idea to (I think) almost all constraint in your model. Note that it may sometimes result in a very big RHS. In these cases it might be better to not apply the idea.

    In your objective you could try to factor out variables C3329 and C3328 to reduce the number of nonlinear terms drastically. What I mean is to turn the term

    ... - 0.016 C119 * C3329 - 0.016 C120 * C3329 - 0.016 C121 * C3329
     - 0.016 C122 * C3329 - 0.016 C123 * C3329 - 0.016 C124 * C3329
       - 0.016 C125 * C3329 - 0.016 C126 * C3329 - 0.016 C130 * C3329
     - 0.016 C131 * C3329 - 0.016 C132 * C3329 - 0.016 C136 * C3329 ...

    into

    ... - 0.016 z * C3329 ...
    ...
    aux_con: - z + C119 + C120 + C121 + C122 + C123 + C124 + C125
    + C126 + C130 + C131 + C132 + C136 = 0
    ...
    z free

    Best regards, 
    Jaromił

    0

Please sign in to leave a comment.