Conditional parameter / slow MIP solving
AnsweredHello!
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
-
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
Please sign in to leave a comment.
Comments
3 comments