3
$\begingroup$

Does Guroib take advantage of the problem structure?

I am working on a large optimization problem with more than 40,000 binary variables and huge number of constraints. below is only one of the constraints:

P_plus>=P

P_plus>=-p

That will be applied on every time step t and every node i.

First formulation: Gurobi consumes 1 minute to solve the model.

Second formulation: Gurobi consumes 9 minutes to solve the model.

# First formulation, efficient formulation:
for i in range(n_b):
    for t in range (n_t):
       m.addConstr(P_plus[i,t]>=P[i,t],name='c0')
       m.addConstr(P_plus[i,t]>=-P[i,t], name='c1')
       
# Second formulation, less efficient formulation:       
m.addConstrs((P_plus[i,t]>=P[i,t] for i in range(n_b) for t in range (n_t)) , name='c0')
m.addConstrs((P_plus[i,t]>=-P[i,t] for i in range(n_b) for t in range (n_t)), name='c1')

Does that mean I should try to aggregate the constraints applied on the same time step and node together?

$\endgroup$
3
  • 1
    $\begingroup$ Might be "performance variability" because of different order of constraints. Try two separate nested FOR loops (like your first formulation, but one for c0 and one for c1) and see if it matches the solve time for your second formulation. $\endgroup$
    – RobPratt
    Jan 7, 2023 at 21:47
  • $\begingroup$ You are right, Dr. RobPratt. But that is weird that the order matters. $\endgroup$ Jan 9, 2023 at 6:55
  • 1
    $\begingroup$ See or.stackexchange.com/questions/3419/… $\endgroup$
    – RobPratt
    Jan 9, 2023 at 13:42

2 Answers 2

3
$\begingroup$

Probably the content here will be helpful.
Using for-loop outside of the gurobi native construct is slightly faster.

$\endgroup$
1
  • $\begingroup$ Thanks, Sutanu. I am referring to the time required to solve the model, not to build it. However, this info would be helpful. $\endgroup$ Jan 9, 2023 at 6:57
3
$\begingroup$

Assuming you're talking about the time required to build the model:

Let's time your two approaches first inside an iPython shell via the %%timeit magic command. Here, I use n_b = 400 and n_t = 100:

In [11]: %%timeit
    ...:
    ...: for i in range(n_b):
    ...:     for t in range (n_t):
    ...:        m.addConstr(P_plus[i,t]>=P[i,t],name='c0')
    ...:        m.addConstr(P_plus[i,t]>=-P[i,t], name='c1')

854 ms ± 9.35 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
In [12]: %%timeit
    ...:
    ...: # Second formulation, less efficient formulation:
    ...: m.addConstrs((P_plus[i,t]>=P[i,t] for i in range(n_b) for t in range (n_t)) , name='c0')
    ...: m.addConstrs((P_plus[i,t]>=-P[i,t] for i in range(n_b) for t in range (n_t)), name='c1')

1.11 s ± 34.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Depending on the other constraints in your model, MVars are probably the better choice if the model building performance matters:

P_plus = m.addMVar((n_b, n_t), name="P_plus")
P = m.addMVar((n_b, n_t), name="P")

Then, you can easily add your constraints as follows:

In [13]: %%timeit
    ...:
    ...: m.addConstr(P_plus >= P)
    ...: m.addConstr(P_plus >= -P)
 
368 ms ± 9.03 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
```
$\endgroup$
1
  • $\begingroup$ Thanks. I am talking about the time required to solve the model, not the time required to build it. However, this info would be helpful. $\endgroup$ Jan 7, 2023 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.