Conditional parameter / slow MIP solving
回答済みHello!
In my model I have a constraint to update a variable
$$ E_{t+1} = E_{t} + \eta_t P_t , 0 \leq t \leq N $$
Now, the value of eta_t should depend on, whether P_t is negative or positive.
I tried to solve this by applying this method https://support.gurobi.com/hc/en-us/community/posts/360078200652-add-a-binary-decision-variable-that-depends-on-another-variable-in-gurobi (and defined two binary variables to decide if P_t should be positive or negative and an auxiliary variable for the sign of P_t)
c = m.addVars(range(LEN), vtype=GRB.BINARY)
d = m.addVars(range(LEN), vtype=GRB.BINARY)
a_cd = m.addVars(range(LEN), vtype=GRB.CONTINUOUS, lb=-1, ub=1)
m.addConstrs(((c[t] == 1) >> (a_cd[t] == 1) for t in range(LEN)))
m.addConstrs(((d[t] == 1) >> (a_cd[t] == -1) for t in range(LEN)))
m.addConstrs((c[t] + d[t] == 1 for t in range(LEN)))
m.addConstrs((eta[t] == c[t] * 0.84 + d[t] * 1.2 for t in range(LEN)))
m.addConstrs((P[t] == a_cd[t] * P_unsigned[t] for t in range(LEN)))
I also tried piecewise linear constraints. However, both made the solver painfully slow, increasing the solving time from ~15 s (if \eta_t is just set to 1) to several hours (so far).
I also tried to change the NumericFocus and MIPFocus parameters to little effect.
Is there a more elegant solution to formulate this problem? (Without binary variables?)
This is the beginning of the log:
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (win64)
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Optimize a model with 87578 rows, 113885 columns and 404319 nonzeros
Model fingerprint: 0xba0c0fad
Model has 17519 quadratic constraints
Model has 26280 general constraints
Variable types: 96365 continuous, 17520 integer (17520 binary)
Coefficient statistics:
Matrix range [9e-09, 5e+01]
QMatrix range [1e+00, 1e+00]
QLMatrix range [1e+00, 1e+00]
Objective range [7e+01, 2e+04]
Bounds range [3e-02, 5e+01]
RHS range [1e-01, 9e+00]
GenCon rhs range [1e+00, 1e+00]
GenCon coe range [1e+00, 1e+00]
Presolve added 36181 rows and 0 columns
Presolve removed 0 rows and 42706 columns
Presolve time: 1.51s
Presolved: 123759 rows, 71179 columns, 375369 nonzeros
Variable types: 62420 continuous, 8759 integer (8757 binary)
Deterministic concurrent LP optimizer: primal and dual simplex (primal and dual model)
Showing first log only...
Root relaxation presolve removed 3 rows and 3 columns
Root relaxation presolved: 123756 rows, 71176 columns, 375363 nonzeros
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
24764 2.8575593e+04 0.000000e+00 4.769768e+05 5s
30448 2.0757423e+04 0.000000e+00 9.284558e+04 10s
33598 1.7423805e+04 0.000000e+00 1.440478e+05 15s
36816 1.3671155e+04 0.000000e+00 4.457890e+05 20s
40212 1.1023125e+04 0.000000e+00 1.239734e+05 25s
42712 9.8143736e+03 0.000000e+00 3.215114e+05 30s
44962 8.9288023e+03 0.000000e+00 4.691737e+05 35s
47262 8.1235558e+03 0.000000e+00 8.236374e+05 40s
49533 7.2015119e+03 0.000000e+00 7.707075e+04 45s
51586 6.5030440e+03 0.000000e+00 9.669210e+04 50s
53223 6.1850317e+03 0.000000e+00 7.064850e+05 55s
54595 5.7517746e+03 0.000000e+00 2.994259e+05 60s
55967 5.5006242e+03 0.000000e+00 5.835930e+04 65s
57927 5.3237764e+03 0.000000e+00 4.877254e+05 71s
59103 5.0113663e+03 0.000000e+00 3.609300e+05 76s
60279 4.7893461e+03 0.000000e+00 1.168366e+06 80s
61847 4.6840011e+03 0.000000e+00 2.553917e+05 85s
63415 4.4285376e+03 0.000000e+00 5.157463e+06 91s
64787 4.1655421e+03 0.000000e+00 1.715687e+05 96s
65963 4.0435126e+03 0.000000e+00 2.160427e+05 100s
67335 3.9214434e+03 0.000000e+00 3.540446e+05 105s
68903 3.8061947e+03 0.000000e+00 8.367486e+04 110s
Concurrent spin time: 50.36s
Solved with dual simplex (primal model)
Root relaxation: objective 1.934411e+03, 76103 iterations, 162.71 seconds (200.86 work units)
Total elapsed time = 175.64s
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 1934.41100 0 5724 - 1934.41100 - - 182s
H 0 0 3904.2892533 1934.41100 50.5% - 210s
0 0 2224.55436 0 5551 3904.28925 2224.55436 43.0% - 277s
H 0 0 3581.6068099 2224.55436 37.9% - 305s
0 0 2254.43485 0 5581 3581.60681 2254.43485 37.1% - 324s
0 0 2255.42507 0 5580 3581.60681 2255.42507 37.0% - 326s
0 0 2255.58508 0 5586 3581.60681 2255.58508 37.0% - 326s
0 0 2255.65055 0 5592 3581.60681 2255.65055 37.0% - 327s
0 0 2255.65453 0 5591 3581.60681 2255.65453 37.0% - 328s
0 0 2792.45300 0 4968 3581.60681 2792.45300 22.0% - 384s
0 0 2800.94407 0 4870 3581.60681 2800.94407 21.8% - 414s
0 0 2802.56965 0 4889 3581.60681 2802.56965 21.8% - 415s
0 0 2803.08050 0 4900 3581.60681 2803.08050 21.7% - 416s
0 0 2803.56238 0 4906 3581.60681 2803.56238 21.7% - 417s
0 0 2804.05010 0 4904 3581.60681 2804.05010 21.7% - 417s
0 0 2804.27880 0 4905 3581.60681 2804.27880 21.7% - 418s
0 0 2804.74341 0 4904 3581.60681 2804.74341 21.7% - 418s
0 0 2804.99448 0 4903 3581.60681 2804.99448 21.7% - 418s
0 0 2805.56531 0 4901 3581.60681 2805.56531 21.7% - 419s-
正式なコメント
-
Gurobi Staff
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 try Gurobot, our chatbot interface offering instant, expert-level support. -
-
-
Hi Michael,
You could try using a big-M formulation as described in How do I model conditional statements in Gurobi?
b = m.addVars(range(LEN), vtype=GRB.BINARY)
m.addConstrs((P[t] >= M*b[t] - M for t in range(LEN)))
m.addConstrs((P[t] <= M*b[t] for t in range(LEN)))
m.addConstrs(((b==1) >> (eta[t] == 0.84) for t in range(LEN)))
m.addConstrs(((b==0) >> (eta[t] == 1.2 ) for t in range(LEN)))In the above, you can either set one \(M\) value for all \(P_t\) or compute individual \(M_t\) values for each index \(t\). It is best to choose the big-M value as tight as possible, e.g., the maximum over the absolute value of the lower and upper bound of each \(P_t\).
Best regards,
Jaromił0 -
-
Hi Jaromił,
thanks for the quick reply and the detailed answer! I'm running it right now and it seems to be faster.
However, the run time is still in the hours range. Maybe the model became just too complex when I turned it into a MIP problem.
Thanks anyway!
Michael
0 -
-
-
Hi Michael,
However, the run time is still in the hours range. Maybe the model became just too complex when I turned it into a MIP problem.
This is indeed very likely the case. By fixing the \(eta_t\) variables, you also remove all corresponding binary variable and thus also all combination of those reducing the search space by a good bit (depending on the cardinality of the \(t\) index). You might want to try to construct a smaller model first and trying to finding tuning parameter by using Gurobi's parameter tuning tool. These parameters may then help and improve performance of the bigger model.
Best regards,
Jaromił0 -
投稿コメントは受け付けていません。
コメント
4件のコメント