Running out of memory

[herge...@gmail.com]

Hello,

I am trying to solve a MIQP problem (quadratic objective function and linear constrains) using the Python API and Gurobi 7.0.0 (linux64). The exact objective function can be found here. It consists of 81 binary variables and several thousands of quadratic objective terms. Unfortunately, the program uses too much memory so that my job running on the university server gets killed.

I set the following parameters hoping to solve the memory problem:

m.setParam("TimeLimit", 86400) 

m.setParam("Threads", 4) 

m.setParam("NodefileStart", 0.5)

Unfortunately, that did not help. What can be done in order to stop Gurobi from using so much memory?

Regards,

Nadja

[Sonja Mars]

Hi Nadja,

Can you post a log file? That would be very helpful to see what is going on.

Thanks and best regards,
Sonja


----
Dr. Sonja Mars
Gurobi Optimization - Technical Support

[Michael Winkler]

Hi Nadja,

maybe you can also share the model (best in mps format, lp is also ok).

Michael

[herge...@gmail.com]

Hi Sonja and Michael,

With the help of a colleague I luckily managed to solve this problem. The issue was that the code was stuck on the m.setObjective() part of my code because of the way I formulated the quadratic objective function. So, the code actually never reached the m.optimize() call, as the job was killed on the server earlier due to memory issues. 

The use of QuadExpr() and expr.addTerms() when formulating the objective function was the game changer. Gurobi seems to struggle a lot when it has to deal with quadratic expressions on its own.

Regards,

Nadja

[Michael Winkler]

Great that you were able to fix the issue, if you'd like you can still add a model if you experience performance issues. Also you might want to try to set the parameter PREQLINEARIZE=1.

Michael

[herge...@gmail.com]

Hi Michael,

I set the parameter m.setParam("PreQLinearize", 1), but that seemed to make my code much slower. My Python script is attached. What it essentially does is select K (<N) products out of a pool of N products so that the mean squared error (MSE) between a reference product and the mean of those K products is minimised. My script uses random data for testing purposes. I'll use real data in a later step. The pool size (N), the subset size (K) and the length of the reference and product vectors (numpoints) can be set in the header of my script. For the application to real data, I'll set them to: N=81, numpoints=400'000 and I'll test it for K=1 up to K=81. 

With N=81, K=20 and numpoints=400000 it takes Gurobi approximately 50min to solve the problem on the university server. Any suggestions how to improve the performance would therefore be welcome.

Regards,

Nadja

[Sonja Mars]

Hi Nadja,

Did I get this right, you have a single constraint and only 81 binary variables?

I used your code with N = 8, K = 20, and numpoints = 400000 to generate a model file. On my notebook I get this log file output, when I set the parameter PreQLinearize=1:

Set parameter PreQLinearize to value 1

Gurobi Optimizer version 7.0.1 build v7.0.1rc0-1-g64d25eb (mac64)

Copyright (c) 2016, Gurobi Optimization, Inc.

Read LP format model from file bigobj.lp

Reading time = 0.00 seconds

: 1 rows, 81 columns, 81 nonzeros

Optimize a model with 1 rows, 81 columns and 81 nonzeros

Model has 3321 quadratic objective terms

Variable types: 0 continuous, 81 integer (81 binary)

Coefficient statistics:

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

  Objective range  [2e-06, 5e-04]

  QObjective range [6e-09, 5e-03]

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

  RHS range        [2e+01, 2e+01]

Found heuristic solution: objective 1.04867

Presolve time: 0.01s

Presolved: 3241 rows, 3321 columns, 9801 nonzeros

Found heuristic solution: objective 1.0486667

Variable types: 0 continuous, 3321 integer (3321 binary)

Root relaxation: objective 1.042017e+00, 2062 iterations, 0.06 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work

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

     0     0    1.04202    0  543    1.04867    1.04202  0.63%     -    0s

H    0     0                       1.0443652    1.04202  0.22%     -    0s

     0     0    1.04365    0  795    1.04437    1.04365  0.07%     -    0s

     0     0    1.04429    0  296    1.04437    1.04429  0.01%     -    0s

Cutting planes:

  Gomory: 17

  Cover: 952

  MIR: 193

  Zero half: 301

Explored 0 nodes (5379 simplex iterations) in 0.63 seconds

Thread count was 4 (of 4 available processors)

Solution count 4: 1.04437 1.04867 1.04867 1.04867 

Pool objective bound 1.04429

Optimal solution found (tolerance 1.00e-04)

Best objective 1.044365184940e+00, best bound 1.044285523687e+00, gap 0.0076%

So it seems Gurobi was able to solve this model to the default MIP gap almost immediately. Is your log file looking similar? Is this model of the size that you are looking for? On what kind of machine are you trying to solve this model?

Best regards, 

[Sonja Mars]

Hi,

I am sorry, there was a typo in my previous email, I used N = 81, K = 20, and numpoints = 400000.

Sonja

> --
>
> ---
> You received this message because you are subscribed to the Google Groups "Gurobi Optimization" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to gurobi+un...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Nadja Herger]

Hi Sonja,

Yes, I have a single linear constraint, a quadratic objective function and 81 binary variables.

I just ran my script again (using python directly instead of first creating a model file) and it actually turns out that with the setting m.setParam("PreQLinearize", 1), the problem is solved within a few seconds (N=81, K=20, numpoints=400000). The content of the log file is below. 

I think what happened is that I tested the PreQLinearize parameter for a small K (e.g. 3). If K is small, setting PreQLinearize=1 actually leads to a longer computing time (53 sec with parameter, 9 sec without). Only for larger K, this parameter actually improves the performance. As soon as I disable PreQLinearize for large K (eg. 30), the model takes considerably longer to solve (6 sec with parameter, 202 sec without).

I am running it on the university server with 16 processors. Each of them has: Intel(R) Xeon(R) CPU E5-2690 0 @ 2.90GHz. But in my Python script I limit the number of threads to 4 usually (m.setParam("Threads", 4)).

Thanks,

Nadja

____________________

* Selecting 20 out of 81 available products.

* Using the solver GUROBI.

* Generate random data

* Set parameters

Changed value of parameter TimeLimit to 86400.0

   Prev: 1e+100  Min: 0.0  Max: 1e+100  Default: 1e+100

Changed value of parameter Threads to 4

   Prev: 0  Min: 0  Max: 1024  Default: 0

Changed value of parameter NodefileStart to 0.5

   Prev: 1e+100  Min: 0.0  Max: 1e+100  Default: 1e+100

Changed value of parameter PreQLinearize to 1

   Prev: -1  Min: -1  Max: 1  Default: -1

* Set objective function.

* Start optimisation

Optimize a model with 1 rows, 81 columns and 81 nonzeros

Model has 3321 quadratic objective terms

Variable types: 0 continuous, 81 integer (81 binary)

Coefficient statistics:

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

  Objective range  [2e-06, 5e-04]

  QObjective range [6e-09, 5e-03]

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

  RHS range        [2e+01, 2e+01]

Found heuristic solution: objective 1.04867

Presolve time: 0.02s

Presolved: 3241 rows, 3321 columns, 9801 nonzeros

Found heuristic solution: objective 1.0486667

Variable types: 0 continuous, 3321 integer (3321 binary)

Root relaxation: objective 1.042017e+00, 2105 iterations, 0.04 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work

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

     0     0    1.04202    0  543    1.04867    1.04202  0.63%     -    0s

H    0     0                       1.0443652    1.04202  0.22%     -    0s

     0     0    1.04365    0  795    1.04437    1.04365  0.07%     -    0s

     0     0    1.04429    0  330    1.04437    1.04429  0.01%     -    0s

Cutting planes:

  Gomory: 11

  Cover: 952

  MIR: 193

  Zero half: 302

Explored 0 nodes (5150 simplex iterations) in 0.70 seconds

Thread count was 4 (of 16 available processors)

Solution count 4: 1.04437 1.04867 1.04867 1.04867

Pool objective bound 1.04429

Optimal solution found (tolerance 1.00e-04)

Best objective 1.044365184910e+00, best bound 1.044285391826e+00, gap 0.0076%

* Number of combinations: 4694436188839116720

* Gurobi

    Minimum MSE: 1.044 (RMSE: 1.022)

    Chosen ensemble member: [ 0  5  6  7 13 17 27 30 34 39 40 47 54 56 62 66 71 73 77 79]

    Elapsed time: 6.899 sec

> To unsubscribe from this group and stop receiving emails from it, send an email to gurobi+unsubscribe@googlegroups.com.

> For more options, visit https://groups.google.com/d/optout.

--

---
You received this message because you are subscribed to a topic in the Google Groups "Gurobi Optimization" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/gurobi/ZOlLSgd9bss/unsubscribe.
To unsubscribe from this group and all its topics, send an email to gurobi+unsubscribe@googlegroups.com.