Warning: max constraint violation exceeds tolerance
OngoingHi, 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)-
Official comment
-
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. -
-
I have found that the problem exists in the log function in the objective. Why addGenConstrLogA brings constraint violation warnings?
0 -
-
-
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 -
Post is closed for comments.
Comments
4 comments