Warning: max constraint violation exceeds tolerance
進行中Hi, I am new to Gurobi, and I am trying to solve a MIP model with a large number of variables (7 continuous, 2880871 integer (2880864 binary)) and constraints.
When solving the model, it gives me warnings: max constraint violation (1.7698e-04) exceeds tolerance and max general constraint violation (1.7698e-04) exceeds tolerance. I am trying to solve this model and my code is presented below.
When I solve the model with two objectives, the results are 251.21 for objective 1 (noise) and 4662 for objective 2 (slot_displace). However, when I use ε-constraint method to solve the model and add slot_displace<=4662 as a constraint, the minimum result for noise is 251.23 with constraint violation warnings. So, what's the problem? Is it owing to the large number of constraints I added? If I use some method to reduce the constraints (e.g., row generation, which solves the model with fewer constraints, and then added violated constraints), could I address the problem?
I'd be grateful if you could provide some guidance.
slot_allocation = gp.Model('slot_allocation')
slot_allocation.setParam('NodefileStart',0.5)
flightslot = slot_allocation.addVars(R,D,T, vtype=GRB.BINARY, name = "X")
#constraints
#1.definition of Xrdt
for d in D:
for r in R:
if Yrd[d][r]==0:
definition=slot_allocation.addConstrs(flightslot[r,d,t]==0\
for t in T)
elif Yrd[d][r]==1:
uniqueness=slot_allocation.addConstr(gp.quicksum(flightslot[r,d,t] \
for t in T)==1)
#2. capacity
for th in Th:
tm=12*th
capacity_total_60=slot_allocation.addConstrs(gp.quicksum(flightslot[r,d,tau] for r in R for tau in range(tm,tm+12))\
<= capacity_60[th][0] for d in D)
capacity_dep_60=slot_allocation.addConstrs(gp.quicksum(flightslot[r,d,tau] for r in Rdep for tau in range(tm,tm+12))\
<= capacity_60[th][1] for d in D)
capacity_arr_60=slot_allocation.addConstrs(gp.quicksum(flightslot[r,d,tau] for r in Rarr for tau in range(tm,tm+12))\
<= capacity_60[th][2] for d in D)
ct=0
for tq in Tq:
tmq=3*tq
if tq % 4==0:
capacity_total_15_0=slot_allocation.addConstrs(gp.quicksum(flightslot[r,d,tau] for r in R \
for tau in range(tmq,tmq+3))<= capacity_15[ct][0] for d in D)
capacity_dep_15_0=slot_allocation.addConstrs(gp.quicksum(flightslot[r,d,tau] for r in Rdep \
for tau in range(tmq,tmq+3))<= capacity_15[ct][1] for d in D)
capacity_arr_15_0=slot_allocation.addConstrs(gp.quicksum(flightslot[r,d,tau] for r in Rarr \
for tau in range(tmq,tmq+3))<= capacity_15[ct][2] for d in D)
if tq % 4==1:
capacity_total_15_1=slot_allocation.addConstrs(gp.quicksum(flightslot[r,d,tau] for r in R \
for tau in range(tmq,tmq+3))<= capacity_15[ct][0] for d in D)
capacity_dep_15_1=slot_allocation.addConstrs(gp.quicksum(flightslot[r,d,tau] for r in Rdep \
for tau in range(tmq,tmq+3))<= capacity_15[ct][1] for d in D)
capacity_arr_15_1=slot_allocation.addConstrs(gp.quicksum(flightslot[r,d,tau] for r in Rarr \
for tau in range(tmq,tmq+3))<= capacity_15[ct][2] for d in D)
if tq % 4==2:
capacity_total_15_2=slot_allocation.addConstrs(gp.quicksum(flightslot[r,d,tau] for r in R \
for tau in range(tmq,tmq+3))<= capacity_15[ct][0] for d in D)
capacity_dep_15_2=slot_allocation.addConstrs(gp.quicksum(flightslot[r,d,tau] for r in Rdep \
for tau in range(tmq,tmq+3))<= capacity_15[ct][1] for d in D)
capacity_arr_15_2=slot_allocation.addConstrs(gp.quicksum(flightslot[r,d,tau] for r in Rarr\
for tau in range(tmq,tmq+3))<= capacity_15[ct][2] for d in D)
if tq % 4==3:
capacity_total_15_3=slot_allocation.addConstrs(gp.quicksum(flightslot[r,d,tau] for r in R\
for tau in range(tmq,tmq+3))<= capacity_15[ct][0] for d in D)
capacity_dep_15_3=slot_allocation.addConstrs(gp.quicksum(flightslot[r,d,tau] for r in Rdep\
for tau in range(tmq,tmq+3))<= capacity_15[ct][1] for d in D)
capacity_arr_15_3=slot_allocation.addConstrs(gp.quicksum(flightslot[r,d,tau] for r in Rarr\
for tau in range(tmq,tmq+3))<= capacity_15[ct][2] for d in D)
ct+=1
#4. turnaround time
turnaround=slot_allocation.addConstrs(gp.quicksum(flightslot[r2,d,t] for t in range(0,k))+gp.quicksum(flightslot[r,d,t] \
for t in range(k-t_min_f,288))<=1 for k in (t_min_f,288) for (r,r2) in F for d in D)
#5. max displacement
max_displacement=slot_allocation.addConstrs((gp.quicksum(abs(t-Trd[d][r])*flightslot[r,d,t]\
for t in T)<=t_max for r in R for d in D),"Max_displacement")
# Objectives
tp = slot_allocation.addVars(D, vtype=GRB.INTEGER, name = "temp")
slot_allocation.addConstrs(gp.quicksum(10*flightslot[r,d,t] for r in R for t in range(0,84))+\
gp.quicksum(flightslot[r,d,t] for r in R for t in range(84,228))+\
gp.quicksum(3*flightslot[r,d,t] for r in R for t in range(228,264))+\
gp.quicksum(10*flightslot[r,d,t] for r in R for t in range(264,288))==tp[d] for d in D)
z=slot_allocation.addVars(D,name='Z')
for d in D:
slot_allocation.addGenConstrLogA(tp[d],z[d],10.0)
noise=10 * gp.quicksum(z[d] for d in D)
slot_displace = gp.quicksum(abs(t-Trd[d][r])*flightslot[r,d,t] for r in R for d in D for t in T)
slot_allocation.setObjectiveN(noise,0,2,GRB.MINIMIZE)
slot_allocation.setObjectiveN(slot_displace,1,1,GRB.MINIMIZE)-
I have found that the problem exists in the log function in the objective. Why addGenConstrLogA brings constraint violation warnings?
0 -
-
-
Gurobi Staff
The code you posted is not self-contained, because \( \texttt{R} \), \( \texttt{D} \), \( \texttt{T} \), and other Python variables are not defined. However, I do have a guess about where the constraint violations come from.
As is the case for all function constraints, Model.addGenConstrLogA() adds a piecewise-linear approximation of the specified function to the model. In your example, Gurobi builds a piecewise-linear approximation of \( y = \log_{10}(x) \), where \( x \) is the variable \( \texttt{tp[d]} \) and \( y \) is the variable \( \texttt{z[d]} \). However, your \( \texttt{tp} \) variables are defined to be nonnegative with no upper bounds. As a result, Gurobi picks a satisfactorily large upper bound \( u, \) then constructs the piecewise approximation of \( y = \log_{10}(x) \) over the domain \( x \in [0, u] \). Even though Gurobi uses a large number of points to construct the piecewise-linear approximation, it can be a poor approximation because these points are thinly stretched across this large domain.
Can you please try defining the tightest possible bounds on your \( \texttt{tp} \) variables? Note that you can control how Gurobi constructs this piecewise-linear approximation using the FuncPieces, FuncPieceError, FuncPieceLength, and FuncPieceRatio attributes (or the parameters with the same names).
If you are feeling especially ambitious, you could define your own piecewise-linear constraint using the Model.addGenConstrPWL() method. In particular, because \( \texttt{tp[d]} \) (\(x\)) is integer-valued, you could construct an exact piecewise-linear representation of \( y = \log_{10}(x) \) by building the approximation from the finite set of points \( \{ (x, \log_{10}(x)) : x \in \{\ell, \ell+1, ..., u-1, u\} \} \), where \( [\ell, u] \) defines the domain of \( x \).
0 -
-
Hi, Eli. Thank you for your help. I have tried defining the bounds on tp variables, and changed the value of the FuncPieces, FuncPieceError, FuncPieceLength, and FuncPieceRatio attributes. The max constraint violation decreases; however, it drops to 1.9367e-06 and then cannot decrease further no matter how I construct this piecewise-linear approximation using these attributes. So, I still got the warnings: max constraint violation (1.9367e-06) exceeds tolerance & max general constraint violation (1.9367e-06) exceeds tolerance.
I was wondering if there is any method to avoid the warnings?
Thank you very much.
0 -
サインインしてコメントを残してください。
コメント
3件のコメント