Gurobi too slow & not enough memory
回答済みHi everyone,
I am trying to solve what a think is a simple (but huge) model.
Given a set of processes (i) that can be executed on different processing units (p) at different timeSteps (t), my model tries to determine how to map each process to an unit and timestep, to minimize the total execution time.
To do so, I've modeled my problem as:
Variables:
- W_i,p,t -> Boolean. 1 if process i is executed on unit p at time t
- C -> Integer. TimeStep when the last process finishes to execute. Objective function. To minimize
Constraints:
- Typical constraints that 2 processes cannot be executed on the same unit at the same time, each process is executed only 1 time, etc.
- Some additional constraints that specific units cannot be used at the same time.
Limits:
- 0 < i <= 100
- 0 < p <= 10
- 0 < t <= 1000
However, when I try to solve my model, the presolving phase takes too much time (see logs below), and, once the systems starts the solve phase, it runs out of memory.
My machine has 64 physical cores with ~250GB of RAM, and I'm using the python version of gurobi.
Things I've tried:
- Reduce the number of threads (down to 16).
- Set "nodefileStart" to 0.5 (Should I decrease it even more? Note I have a lot of RAM on my machine).
- Set "presparsify" to 2, to speed up the process.
- Set "presolve" to 1.
Could you give me a clue of how to (1) speed up the model, (2) don't run out of memory, (3) optimize the model to avoid previous problems?
Thank you in advance. Here is an extract of the log, in case you want to check it:
Gurobi Optimizer version 10.0.1 build v10.0.1rc0 (linux64)
CPU model: Intel(R) Xeon(R) Platinum 8358 CPU @ 2.60GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 64 physical cores, 64 logical processors, using up to 16 threads
Optimize a model with 1610964 rows, 329176 columns and 2023760550 nonzeros
Model fingerprint: 0x279400ac
Variable types: 1 continuous, 329175 integer (329175 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+06]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 6e+02]
RHS range [1e+00, 1e+06]
Presolve removed 0 rows and 0 columns (presolve time = 62s) ...
Presolve removed 0 rows and 0 columns (presolve time = 70s) ...
Presolve removed 0 rows and 0 columns (presolve time = 78s) ...
Presolve removed 0 rows and 16800 columns (presolve time = 90s) ...
Presolve removed 224 rows and 16800 columns (presolve time = 97s) ...
[ ... ]
Presolve removed 964975 rows and 26770 columns (presolve time = 7842s) ...
Presolve removed 964975 rows and 26770 columns (presolve time = 7874s) ...
Presolve removed 952659 rows and 14454 columns
Presolve time: 7874.48s
Presolved: 658305 rows, 314722 columns, 640860989 nonzeros
Variable types: 0 continuous, 314722 integer (312375 binary)
Found heuristic solution: objective 599.0000000
Deterministic concurrent LP optimizer: primal and dual simplex (primal and dual model)
Showing first log only...
Finished (killed)
-
-
Gurobi Staff
Hi LC,
I doubt parameters are going to be able to come to the rescue in this instance. Time indexed models for machine scheduling grow pseudo-polynomially in size and soon become intractable.
Alternative reformulation will be the best approach here. If your units (a.k.a "machines") are identical, and each process is executed once, and once only, then you can use a formulation which does not require binary variables, or constraints, to be indexed by unit which will cut down the size significantly since you have M=10 units.
\begin{eqnarray}
\sum_t w_{it}=1, \forall i\\
\sum_i \sum_{s = t-l_i+1}^t w_{is} \leq M, \forall t\\
\end{eqnarray}Once the solve is finished you won't have an assignment of process to unit, but you are guaranteed to be able to construct a valid one trivially by iterating through processes in order of start time and assigning them to idle units. I'd try this approach first as I suspect it would require little modification to your existing code.
Another alternative is to try a disjunctive model, where variables are indexed by unit, but not time. An example for job-shop problem (which is similar to identical parallel machine scheduling) can be found in this paper https://tidel.mie.utoronto.ca/pubs/JSP_CandOR_2016.pdf. You would have to adapt it for your specific problem.
- Riley
0 -
-
Hi Riley,
Thank you for the answer!
I totally agree that reformulating the problem is the best approach here, but I'm not sure I can adapt my problem to the formulation you are proposing. My scenario has two particularities:
- The execution time of each process/task depends on the machine/unit it is executed.
- Not all machines can be utilized simultaneously. I have specific constraints saying that specific machines cannot be used simultaneously as other specific machines. For example, in a scenario with machines A, B and C, I could have constraints like:
- A cannot be used at the same time as B
- A cannot be used at the same time as C
(but B and C can be used simultaneously)
I will check the paper you mention and see if I can formulate my problem like a disjuctive model.Thank you again for the answer!
Bests
Luis
0 -
-
-
Hi Luis,
I see, this does complicate things, although without fleshing out the details I think a disjunctive model could work with some tweaking.
Perhaps it may help to think of machines that cannot be simultaneously used as one unit with different processing times (and surely we'd always choose whichever machine gives the smallest processing time for that task).
If the problem extends to "no more than n machines can be concurrently running amongst this set M of machines" then that will complicate it further and then I think disjunctive model would not be appropriate.
- Riley
0 -
サインインしてコメントを残してください。
コメント
3件のコメント