Skip to main content

MIP with bilinear constraints not converging for large datasets

Answered
Elizabeth Griffin
  • Gurobi-versary
  • First Question

We are trying to minimize the sum of absolute deviations between known values, d(i), and unknown values, b(j) , where x(i,j) is an indicator variable to switch values b(j) on and off:

We have transformed this into the following LP problem to eliminate the absolute value:

Note that the set j is typically small, i.e. j = {1,...,4}, but the set i can be rather big. We have had no problems solving this for smaller sets (where i has ~30-50 instances) but it appears the branch-and-cut algorithm is not converging for a large number of instances (~800). The MIP gap stops steadily decreasing after a while and the optimal solution is not identified after many hours.

The output with a run using a set of 50 instances for i is copied below. We wonder if you have any recommendations for us on how to move forward?

Optimize a model with 50 rows, 253 columns and 150 nonzeros

Model fingerprint: 0x23af6a5d

Model has 50 quadratic constraints

Variable types: 103 continuous, 150 integer (150 binary)

Coefficient statistics:

  Matrix range     [1e+00, 1e+00]

  QMatrix range    [1e+00, 1e+00]

  QLMatrix range   [1e+00, 1e+00]

  Objective range  [1e+00, 1e+00]

  Bounds range     [1e+00, 1e+00]

  RHS range        [1e+00, 1e+00]

  QRHS range       [3e+01, 9e+03]

Presolve removed 8 rows and 40 columns

Presolve time: 0.00s

Presolved: 336 rows, 591 columns, 966 nonzeros

Presolved model has 252 SOS constraint(s)

Variable types: 339 continuous, 252 integer (252 binary)

Found heuristic solution: objective 30730.716060

 

Root relaxation: objective 2.182787e-11, 194 iterations, 0.00 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work

 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

 

     0     0    0.00000    0   55 30730.7161    0.00000   100%     -    0s

H    0     0                    28667.960880    0.00000   100%     -    0s

H    0     0                    28370.626800    0.00000   100%     -    0s

H    0     0                    28339.654500    0.00000   100%     -    0s

     0     0    0.00000    0   55 28339.6545    0.00000   100%     -    0s

H    0     0                    23960.171280    0.00000   100%     -    0s

H    0     2                    20460.301380    0.00000   100%     -    0s

     0     2    0.00000    0   55 20460.3014    0.00000   100%     -    0s

H   26    32                    15213.593760    0.00000   100%   6.9    0s

H   31    40                    14036.646360    0.00000   100%   6.5    0s

H  230   226                    13516.311720    0.00000   100%   2.6    0s

H  231   274                    11980.085640    0.00000   100%   2.6    0s

H  579   388                    11373.028560    0.00000   100%   2.7    0s

H  855   476                    11286.306120    0.00000   100%   2.5    0s

H 1680   882                    10096.969800    0.00000   100%   3.0    0s

* 3195  1352             122    9886.3581600    0.00000   100%   2.9    0s

 110405 62224 4936.98462   82   25 9886.35816 1672.50420  83.1%   2.3    5s

*158012 86607             123    9824.4135600 1864.53246  81.0%   2.3    7s

*185355 99999             119    9675.7465200 1963.64382  79.7%   2.3    8s

H189299 99353                    9366.0235200 1976.03274  78.9%   2.3    8s

H198970 95768                    9056.3005200 2013.19950  77.8%   2.3    8s

 239464 112753 6863.46168   55   40 9056.30052 2155.67208  76.2%   2.4   10s

 378496 167045 7210.35144   82   24 9056.30052 2521.14522  72.2%   2.4   15s

 520273 223463 7464.32430   84   25 9056.30052 2787.50700  69.2%   2.4   20s

 656735 275370     cutoff   79      9056.30052 2973.34080  67.2%   2.4   25s

 800650 328670     cutoff   50      9056.30052 3128.20230  65.5%   2.4   30s

 937937 379072 8758.96644  100   16 9056.30052 3245.89704  64.2%   2.4   35s

 1063824 422718 4410.45552   76   29 9056.30052 3338.81394  63.1%   2.5   40s

 1199580 471967     cutoff   63      9056.30052 3413.14746  62.3%   2.5   45s

 1331451 518817 8418.27114   75   25 9056.30052 3481.28652  61.6%   2.5   50s

 1454296 564550 infeasible   79      9056.30052 3537.03666  60.9%   2.5   55s

 1586617 612777 6045.79296   69   36 9056.30052 3598.98126  60.3%   2.5   60s

 1725046 666270 8771.35536   70   23 9056.30052 3648.53694  59.7%   2.5   65s

 1861514 719035 7916.51988   71   30 9056.30052 3685.70370  59.3%   2.5   70s

 1984004 768786     cutoff   64      9056.30052 3716.67600  59.0%   2.6   75s

 2109620 816836 8021.82570   88   21 9056.30052 3747.64830  58.6%   2.6   80s

 2240454 865328     cutoff   64      9056.30052 3778.62060  58.3%   2.6   85s

 2372751 916189 8523.57696   82   28 9056.30052 3815.78736  57.9%   2.6   90s

 2513586 971021     cutoff   62      9056.30052 3834.37074  57.7%   2.6   95s

 2646458 1023280 7204.15698   65   47 9056.30052 3865.34304  57.3%   2.6  100s

 2774219 1072064 6590.90544   71   24 9056.30052 3890.12088  57.0%   2.6  105s

 2894969 1120277 6690.01680   60   51 9056.30052 3921.09318  56.7%   2.6  110s

 3027147 1172727     cutoff   73      9056.30052 3933.48210  56.6%   2.6  115s

 3150331 1220312 5420.15250   73   25 9056.30052 3958.25994  56.3%   2.6  120s

 3287453 1276267     cutoff   68      9056.30052 3970.64886  56.2%   2.6  125s

 3418969 1325799 4453.81674   82   25 9056.30052 4001.62116  55.8%   2.6  130s

 3533478 1371380 5395.37466   56   62 9056.30052 4020.20454  55.6%   2.6  135s

 3648130 1415594     cutoff   73      9056.30052 4038.78792  55.4%   2.6  140s

 3781924 1469562 5866.15362   67   34 9056.30052 4057.37130  55.2%   2.6  145s

 3912776 1520285     cutoff   73      9056.30052 4075.95468  55.0%   2.6  150s

 4041821 1569094 7086.46224   72   35 9056.30052 4094.53806  54.8%   2.6  155s

 4159513 1613057 8969.57808   72   39 9056.30052 4119.31590  54.5%   2.6  160s

 4286844 1660020 6021.01512   56   63 9056.30052 4137.89928  54.3%   2.6  165s

 4423385 1713956 7941.29772   68   30 9056.30052 4156.48266  54.1%   2.6  170s

 4543739 1758020     cutoff   66      9056.30052 4175.06604  53.9%   2.6  175s

 4680477 1809728 7997.04786   83   24 9056.30052 4193.64942  53.7%   2.6  180s

 4817198 1859578 8957.18916   66   36 9056.30052 4212.23280  53.5%   2.6  185s

 4950966 1907940     cutoff   60      9056.30052 4237.01064  53.2%   2.6  190s

 5085817 1959082     cutoff   68      9056.30052 4249.39956  53.1%   2.6  195s

 5209831 2002345 6002.43174   67   42 9056.30052 4267.98294  52.9%   2.6  200s

 5333897 2051093     cutoff   73      9056.30052 4280.37186  52.7%   2.6  205s

 5461014 2099327 5785.62564   76   31 9056.30052 4298.95524  52.5%   2.6  210s

 5592573 2146103     cutoff   65      9056.30052 4311.34416  52.4%   2.6  215s

 5722681 2192570     cutoff   69      9056.30052 4329.92754  52.2%   2.6  220s

 5839533 2235961 4831.67880   68   29 9056.30052 4342.31646  52.1%   2.6  225s

 5946066 2272917     cutoff   75      9056.30052 4360.89984  51.8%   2.6  230s

 6046540 2310932 6504.18300   63   47 9056.30052 4367.09430  51.8%   2.6  235s

 6160057 2349711 7662.54702   67   30 9056.30052 4379.48322  51.6%   2.6  240s

 

0

Comments

2 comments

Date Votes
  • Official comment
    Simranjit Kaur
    • Gurobi Staff
    Edited
    This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
  • Maliheh Aramon
    • Gurobi Staff
    Edited

    Hi Elizabeth, 

    We can think of improving the performance of Gurobi from two different aspects: modelling and parameter tuning. 

    Modeling:

    • Gurobi supports modelling simple general constraints such as absolute values directly. To model a constraint in the form of y=|x|, you can use the Gurobi general constraint Model.addGenConstrAbs(). As explained in the documentation, each general constraint has an equivalent MIP formulation that consists of linear and SOS constraints, and possibly auxiliary variables. You can model these constraints yourself without using Gurobi general constraints as you already did. However, using Gurobi general constraints might have the extra benefit of simplifying the equivalent MIP formulation.
    • Gurobi does not support strict inequality constraints because of the floating-point arithmetic and defining the feasible set as an open set. You need to change b>0 to b≥0 (or to b≥ϵ if you want b to be strictly positive).
    • It is a good practice to define lower and upper bounds for the decision variables. You might want to define an upper bound for your decision variables b. Given your model, it seems max(d) would work if d values are always positive.
    • Make sure that you are using the latest version of Gurobi Optimizer (version 9.1.2). Running the model on a machine with more cores can help as well.

    Parameter tuning: 

    It would be best if you can share the log file of your hard instance with i={1,2,...,800}. You might want to consider tuning the parameters of your model using the Gurobi Parameter Tuning Tool. This is an automated tool and you do not need to provide any parameter settings. However, if you do not have access to enough computational resources to speed up the tuning process, you can also consider experimenting with the following parameters to gain more insight into your model.

    • Presolve=2 and/or PreSparsify=1. The former applies presolving more aggressively and can result into a smaller model to optimize. The latter might help to reduce the number of non-zeros.
    • If the best bound is the bottleneck, consider Cuts=2 or 3. This applies cuts more aggressively and can tighten the relaxation, resulting into a tighter bound.
    • If the incumbent solution is the bottleneck, consider increasing the amount of time spent in the MIP heuristics by Heuristics=0.1 or higher. You might also want to increase the frequency of applying the RINS heuristic.
    • Symmetry, MIPFocus, ImproveStartGap, and ImproveStartTime are other parameters you can consider experimenting with.
    • If it is easy to build a good heuristic solution for your model, it is a very good idea to provide that solution as a start solution to Gurobi.

    Please consider the above just as guidelines and be aware that parameters in Gurobi are inter-dependent and it is impossible to precisely know their effects rather by experimentation. 

     

    Best regards,

    Maliheh

    1

Post is closed for comments.

Didn't find what you were looking for?

New post