Constraints doesn't work
AnsweredHi,
I'm trying to translate an LP problem into Gurobi using python but my program is not working. I spent several days to debug it but it's still not working. I appreciate any help!
Specifically, our LP problem can be interpreted as: We have many clients and each of them holds samples of different classes. We want to select clients and tell them how many samples they should run for each class(denoted as quantity var).
Our objective is to minimize the time of the slowest client.
Our constraints are:
- The summation of samples of each class we selected should above our predefined threshold
- The number of samples ran on each client should not exceed its capacity
I've attached my code and some comments for better understanding below.
# Create a new model
m = gp.Model("client_selection")
qlist = []
for i in range(num_of_clients):
for j inrange(num_of_class):
qlist.append((i, j))
slowest = m.addVar(vtype=GRB.CONTINUOUS, name="slowest", lb = 0.0)
quantity = m.addVars(qlist, vtype=GRB.INTEGER, name="quantity", lb = 0) # # of example for each class
# Each element in time list is the time for each client to finish their job. speed -> time per example and bw is the time to transfer information.
time_list = [((gp.quicksum([quantity[(i, j)] for j in range(num_of_class)])*speed[i])/1000. + bw[i]) for i in range(num_of_clients)]
# The objective is to minimize the slowest
m.setObjective(slowest, GRB.MINIMIZE)
# Minimize the slowest
for t in time_list:
m.addConstr(slowest >= t, name='slow')
# Preference Constraint
for i in range(num_of_class):
m.addConstr(gp.quicksum([quantity[(client, i)] for client in range(num_of_clients)]) >= preference[i], name='preference_' + str(i))
# Capacity Constraint
m.addConstrs((quantity[i] <= datas[i[0]][i[1]] for i in qlist), name='capacity_'+str(i))
I think there is something wrong with the code because I wrote some test cases and they didn't work. I'm happy to explain anything that is not clear
Thanks in advance!
-
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 why not try our AI Gurobot?. -
-
-
Hi Xiangfeng,
Do you have a few lines of code that show how the data ( \(\texttt{speed}\), \(\texttt{bw}\), etc.) is defined for a small instance of the problem?
Thanks,
Eli
0 -
-
Hi Eli,
Thanks for your prompt reply! For example, if there are two classes of interest and there are 5 clients.
num_of_class = 2
num_of_clients = 5
preference = [50, 50] # We want 50 samples of class 1 and 50 samples of class 2
datas = [[15, 5], [35, 20], [40, 20], [30, 15], [70, 19]] # client 1 holds 15 samples of class 1 and 5 samples of class 2 etc.
speed = [0.13, 0.10, 0.15, 0.20] # client 1 needs .013 seconds to process a sample , client 2 needs .010 secs, etc.
bw = [20, 10, 23, 5] # client 1 needs 20 secs to transmit the information ...Please let me know if you have any questions. Thansk so much!!!
0 -
-
Hi Eli,
Sorry to bother you, but any ideas?
Thanks,
Xiangfeng
0 -
-
-
Hi Xiangfeng,
I added an element to your \( \texttt{speed} \) and \( \texttt{bw} \) lists. They each contain four elements, but \( \texttt{num_of_clients = 5} \).
speed = [0.13, 0.10, 0.15, 0.20, 0.25]
bw = [20, 10, 23, 5, 10]What exactly isn't correct with the solution? The model has the following constraints:
slowest >= 20 + 0.00013 quantity[0,0] + 0.00013 quantity[0,1]
slowest >= 10 + 0.0001 quantity[1,0] + 0.0001 quantity[1,1]
slowest >= 23 + 0.00015 quantity[2,0] + 0.00015 quantity[2,1]
slowest >= 5 + 0.0002 quantity[3,0] + 0.0002 quantity[3,1]
slowest >= 10 + 0.00025 quantity[4,0] + 0.00025 quantity[4,1]The values of \( \texttt{bw} \) dominate the right-hand sides of these inequalities, since the \( \texttt{quantity} \) variables have tiny coefficients and relatively small upper bounds:
quantity[0,0] <= 15
quantity[0,1] <= 5
quantity[1,0] <= 35
quantity[1,1] <= 20
quantity[2,0] <= 40
quantity[2,1] <= 20
quantity[3,0] <= 30
quantity[3,1] <= 15
quantity[4,0] <= 70
quantity[4,1] <= 19So, the optimal solution is to assign the samples such that the client with the highest transmission time doesn't run any samples. In this case, the optimal objective function value is 23 (the largest value in \( \texttt{bw} \)).
Maybe a client's processing time \( \texttt{bw} \) should only be counted if the client is assigned at least one sample?
If the model doesn't seem correct, you can use Model.write() to write an LP file to visually inspect the model. E.g.:
m.write('model.lp')Thanks,
Eli
0 -
-
>Maybe a client's processing time should only be counted if the client is assigned at least one sample?
Yes! I think that might be the problem. I'll check this. Thanks so much!
0 -
-
Hi Eli,
I really appreciate your help and I'm trying to fix the problem. However, it seems like it didn't work. (the slowest is smaller than the data transmission time)
status = m.addVars([i for i in range(num_of_clients)], vtype = GRB.BINARY, name = 'status') # Binary var indicates the selection status
for i in range(num_of_clients):
m.addGenConstrIndicator(status[i], True, gp.quicksum([quantity[(i, j)] for j in range(num_of_class)]) >= 0.9)
# Minimize the slowest(I removed bw[i] from the time_list)
for idx, t in enumerate(time_list):
m.addConstr(slowest >= t + status[idx] * bw[idx], name=f'slow_{idx}')I think the problem is this line:
m.addGenConstrIndicator(status[i], True, gp.quicksum([quantity[(i, j)] for j in range(num_of_class)]) >= 0.9)
What's the correct approach to set this indicator constraint? I think >= 0.9 doesn't work, but I don't know how to solve it
Thanks so much!
0 -
-
-
Hi Xiangfeng,
Right now, that constraint is structured for the implication \( \texttt{status[i]} = 1 \implies f_i(x) \geq 0.9 \), where \( f_i(x) \) represents the quantity of samples assigned to client \( i \). With this approach, it can (and will) happen that \( f_i(x) \) is greater than \( 0.9 \), but \( \texttt{status[i]} \) is equal to \( 0 \). Thus, the \( \texttt{bw} \) terms on the RHS of the "slow" constraints won't ever matter.
I think what you really want is the converse: \( f_i(x) \geq 1 \implies \texttt{status[i]} = 1 \). In other words, if any quantity of samples is assigned to client \( i \), we force \( \texttt{status[i]} \) to \( 1 \), which adds the corresponding \( \texttt{bw} \) value to that client's "slow" constraint. We can rewrite this implication in terms of the (logically equivalent) contrapositive: \( \texttt{status[i]} = 0 \implies f_i(x) \leq 0 \). Note that the right side of this implication should really be \( f(x) < 1 \), but since \( f_i(x) \) is integer-valued, this is equivalent to \( f_i(x) \leq 0 \).
Then, following the documentation for Model.addGenConstrIndicator():
status = m.addVars(num_of_clients, vtype=GRB.BINARY, name='status')
for i in range(num_of_clients):
m.addGenConstrIndicator(status[i], False, quantity.sum(i, '*') <= 0)Does this work for you?
Eli
0 -
-
Hi Eli,
I think you're right. I think didn't understand how Model.addGenConstrIndicator() works before. Thanks so much for your help.
Xiangfeng
0 -
Post is closed for comments.
Comments
9 comments