Assignement, dependencies and calculation of variables
Answered
Hey!
I am a student who has rarely seen Gurobi during her studies. Now I want to work out a MIP about revenue maximization with python and gurobi.
To work this out "by hand", I would normally define my variables, set up my constraints and formulate my objective function. But this topic here is a bit to complex to do "by hand"/without a solver. So I started with gurobi by plugging in variables , constraints and the objective function.!
So my objective function is as follows:
\[\begin{align*}
\max \sum\limits_{s\in S} p^s\;\bigg(\sum\limits_{f \in F} r_{f}\;\bigg(\sum\limits_{t=\hat t}^{t^s+1} x_{ft} +\sum\limits_{t=t^s}^{0} x_{ft}^s\bigg)&-\;\sum\limits_{i=1}^{K} b_{i}\alpha_{i}^s \bigg)
\end{align*}\]
There are several constraints that apply as well. I just thought this would be too much to post it all.
Basically, this is about ticket revenue. What I want to optimize are
1.\(x_{ft}\) :the number of tickets that can be offered in fare class f at time t.
2: \(x_{ft}^s\) :the number of ticktes that can be offered in fare class f (given)at time t (range from 360-0 in increments of 1) in scenario s where the capacity of total tickets is updated at time \(t^s\) in the booking horizon with a corresponding probability \(p^s\) (given). \(alpha _i\) is an indicator variable , indicating if a denied boarding occurs for the ith passenger. and \(b_i\) are the costs for the ith denied person.
So there is a problem of the form max probability*(income -losses). But with many different variables.
My questions now:
1.Did I assign the variables that I want to optimize for correct?
from typing import BinaryIO
x = m.addVar(fares,times, vtype=BRB.INTEGER,,name='x') #x_ft
y = m.addVar(fares,times,vtype=BRB.INTEGER,obj=scenarios,name='y') #x_ft^s
t = m.addVar(vtype=GRB.INTEGER, name="t") #starting time
a=pd.series(m.addVars(sampled_tickers, #denial indicator
lb=0
ub=1
vtype=gp.GRB.Binary),
index=sampled_tickers))
z=pd.series(m.addVars(sampled_tickers, #denial indicator at time t^s, needed for constraint,very similar to a_i
lb=0
ub=1
vtype=gp.GRB.Binary),
index=sampled_tickers))
# constraint (1) guarantees that the number of sold tickets adjusted by potential denied boardings does not exceed the capacity in each scenario
c1=m.addConstr(quicksum(quicksum((x[f,t])for f in fares for times[:t_last-1])+quicksum(y[f,t,s]for f in fares for t in times[:t_last-1] for s in scenarios)))<=(c[s]+quicksum(a[i,s]))for s in scenarios)
times = np.arrange(360,0)
fares = ['f1', 'f2', 'f3', 'f4', 'f5', 'f6', 'f7', 'f8', 'f9'] #further depended on value and demand which I set up in a multidict
scenarios = ['sce1', 'sce2', 'sce3','sce4'] #every scenario comes with time, probaility and capacity, set up in several multidict
K=10 # K= bound of number of denied boardings...
a=[1,1,0,0,0,0,1,1,0,0] #example!! 10 sold tickets, 4 denied boardings,
summe1 = 0
count = 0
for i in range(K):
if count<2: #example from the second denied boarding use max denied boarding costs!
if a[i]!=0:
b.append(b0_max*(1.1**i))
summe1 = summe1 + b[i]
count = count + 1
else:
b.append(0)
else:
if a[i]!=0:
summe1 = summe1 + 1
print(summe1)
print(b)
print(count)
-
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. -
-
-
Hi Liz,
1.Did I assign the variables that I want to optimize for correct?
from typing import BinaryIO
x = m.addVar(fares,times, vtype=BRB.INTEGER,,name='x') #x_ft
y = m.addVar(fares,times,vtype=BRB.INTEGER,obj=scenarios,name='y') #x_ft^s
t = m.addVar(vtype=GRB.INTEGER, name="t") #starting time
a=pd.series(m.addVars(sampled_tickers, #denial indicator
lb=0
ub=1
vtype=gp.GRB.Binary),
index=sampled_tickers))
z=pd.series(m.addVars(sampled_tickers, #denial indicator at time t^s, needed for constraint,very similar to a_i
lb=0
ub=1
vtype=gp.GRB.Binary),
index=sampled_tickers))You need a set of \(x\) and \(y\) variables which you correctly define over fares and times. However, you are using the addVar method which adds only 1 variable. Thus, this will not work. You should instead use the addVars method.
You say that \(y\) depends on scenarios, but you set the objective coefficients of \(y\) equal to your scenarios list. If you want to use scenarios as an index, you should go with
y = m.addVar(fares,times,scenarios,vtype=BRB.INTEGER,name='y') #x_ft^s
I am not sure what you are trying to achieve with the \(t\) variable but it is defined correctly.
Why are you trying to make a pd.series out of the tupledict generated by the addVars method? If you define \(a\) as
a = m.addVars(sampled_tickers, #denial indicator
vtype=gp.GRB.Binary)you can access \(a\) variables via
a[i] # where i is in sampled_tickers
The same holds for \(z\).
2. x depends on fares × and y depends on fares, time and scenario.Did I apply the dependencies in the following constraint correct?# constraint (1) guarantees that the number of sold tickets adjusted by potential denied boardings does not exceed the capacity in each scenario
c1=m.addConstr(quicksum(quicksum((x[f,t])for f in fares for times[:t_last-1])+quicksum(y[f,t,s]for f in fares for t in times[:t_last-1] for s in scenarios)))<=(c[s]+quicksum(a[i,s]))for s in scenarios)
times = np.arrange(360,0)
fares = ['f1', 'f2', 'f3', 'f4', 'f5', 'f6', 'f7', 'f8', 'f9'] #further depended on value and demand which I set up in a multidict
scenarios = ['sce1', 'sce2', 'sce3','sce4'] #every scenario comes with time, probaility and capacity, set up in several multidictPlease have a look at the documentation of the quicksum function. You have to provide a list when using quicksum. However, you \(\texttt{for}\)-loops are outside of the quicksums. Then, there is an outer quicksum which loops over nothing. You should try something like
c1=m.addConstr(quicksum(x[f,t] for f in fares for times[:t_last-1])+quicksum(y[f,t,s] for f in fares for t in times[:t_last-1] for s in scenarios)<=quicksum(a[i,s] + c[s] for s in scenarios))Note that in the above, the definition of index \(i\) in \(\texttt{a[i,s]}\) is missing. You have to add it in order to make the constraint work. It would be easier to check this constraint if you would provide it as a formula. In your post, you only provided the formula for the objective function. The above could would generate the following constraint
\[\begin{align*}
\sum_{f} \sum_t^{t_{last}-1} x_{f,t} + \sum_{f} \sum_{t}^{t_{last}-1} \sum_s y_{f,t,s} \leq \sum_s (a_{i,s}+c_s)
\end{align*}\]3. For calculating the denied boarding costs, I played a little bit with python but have no idea how to implement this calculation in my gurobi model:
I am not sure what exactly you want to model here, but you can use indicator constraints to model "if \(a_i = 0\) then enforce some linear constraint. Also the Knowledge Base article How do I model conditional statements in Gurobi? might be helpful.
Best regards,
Jaromił0 -
-
Hi Jaromil,
Thank you very much for your afford in corrrecting this!!! I very much appreciate your feedback!
1.I changed the addVar to the AddVars method, which totally makes sense to me because I need more than one variable.
2. Reading the documentatio about objective coefficients is confusing me. What is a objective coeffcient?
But since y depends on fares, times and scenarios in the same manner, your correction makes way more sense.
t is the variable time that runs from 360 to 0 days (starting period for booking until departure).
I thought in the meantime that it is probably better to use times in the following way:
times = np.arrange(360,0). What I need is my model to go through each day(360,359,358...) and check, whether a number of tickets should be offerend (x) or a scenario starts (if t=t^s) which would lead to a number of tickets to be offered (y).For this iteration I usedtimes[:t_last-1] in my quicksum .But if I understand it, I don' t need to need to add a variable for this iteration. (So t=m.addVar can be ommitted?)3. a[i]. If I understand this corectly, this gives me a list with zeroes and ones which is exactly what I need.4. For further understanding I provide you the whole MIP that I want to optimize:\(\begin{equation}
\begin{aligned}
max \sum\limits_{s\in S} p^s\;\bigg(\sum\limits_{f \in F} r_{f}\;\bigg(\sum\limits_{t=\hat t}^{t^s+1} x_{ft} +\sum\limits_{t=t^s}^{0} x_{ft}^s\bigg)&-\;\sum\limits_{i=1}^{K} b_{i}\alpha_{i}^s \bigg) \\
\sum\limits_{f \in F} \;\bigg(\sum\limits_{t=\hat t}^{t^s+1} x_{ft} +\sum\limits_{t=t^s}^{0} x_{ft}^s\bigg) &\leq c^s + \sum \limits_{i=1}^{K}\alpha_{i}^s \quad &&\forall\; s \in S \\
\sum\limits_{i=1}^{K}\alpha_{i}^s &\leq Kz^s\quad &&\forall\; s \in S\\
x_{ft} &\leq D_{ft}\quad &&\forall\; t\in T, f \in F\\
x_{ft}^s &\leq D_{ft}(1-z^s)\quad &&\forall\; t\in T, f \in F, s\in S\\
x_{ft},x_{ft}^s &\geq 0\quad &&\forall\; t\in T, f \in F, s\in S \nonumber\\
\alpha_{i}^s,z^{s}&\in \{0,1\}\quad &&\forall\; i\in \{1,...,K\},s\in S \nonumber
\end{aligned}
\end{equation}\)0 -
-
Why doesn't this Latex transfer to math symbols?
I even tried it without the equation and alignment environment...0 -
-
Ok, but I hope,that it will still help you to further understand my topic.
Some explanation for the constraints:
Constraint 1 makes sure that the number of tickets together in the global and scenario-based strategy minus the denied boardings do not exceed the existing capacity.
Constraint 2 defines the the total number of denied boardings in a scenario is smaller that the acceptable bound (so K is a variable) if a scenario has a necessity for denied boardings.
Constraint 3 makes sure that the number of offered tickets cannot be larger than the respective demand (which follows a gamma distribution according to a table provided which also needs to be implemented)
Constraint 4 makes sure that if there are already denied boardings, that the number of tickets that can be offered is 0.
Constraint 5 defines the number of tickets to be offered to be zero or positive.I the meantime I will go through the documentationhints you provided me, thanks!
Best regards,
Liz0 -
-
5.If quicksum can only go through lists, it can't iterate through my multidicts..?:
For example, when times reaches the scenariotime (scetime) I want it to go through the corresponding scenario with the resulting capacity and probability and calculate how many tickets should be offered before the scenario and after the capacity update in certain fare classes and hence over all scenarios find the max revenue.
Here are my multidicts:
scenarios, capacities, scetime, probability = gp.multidict({
('sce1'): [50,60,0.2],
('sce2'): [50,7,0.1],
('sce3'): [110,7,0.2],
('sce4'): [100,0,0.5],
})The same happens for my fares, the corresponding values and the demand per fare.# Fares and values for all t \in times.
fares, values, demand = gp.multidict({
('f1'): [1.00,0.07],
('f2'): [0.78,0.08],
('f3'): [0.65,0.05],
('f4'): [0.53,0.06],
('f5'): [0.41,0.1],
('f6'): [0.31,0.08],
('f7'): [0.22,0.16],
('f8'): [0.16,0.25],
('f9'): [0.12,0.15],
})So should I transform the multidict into lists?Regards,Liz0 -
-
-
Hi Liz,
2. Reading the documentatio about objective coefficients is confusing me. What is a objective coeffcient?
But since y depends on fares, times and scenarios in the same manner, your correction makes way more sense.
t is the variable time that runs from 360 to 0 days (starting period for booking until departure).
I thought in the meantime that it is probably better to use times in the following way:
times = np.arrange(360,0). What I need is my model to go through each day(360,359,358...) and check, whether a number of tickets should be offerend (x) or a scenario starts (if t=t^s) which would lead to a number of tickets to be offered (y).
For this iteration I used
times[:t_last-1] in my quicksum .But if I understand it, I don' t need to need to add a variable for this iteration. (So t=m.addVar can be ommitted?)An objective coefficient is the coefficient of the particular variable in the objective function. For example, if you add a variable via
x = m.addVar(obj=2,name="x")
then your objective function will have a linear term \(+ 2 \cdot x\).
I would recommend to have a look at our Python webinar series starting with Python I: Introduction to Modeling with Python - Gurobi. This should be a great help in getting started with gurobipy.
You are using a time index, so usually an additional variable \(t\) is not needed.
3. a[i]. If I understand this corectly, this gives me a list with zeroes and ones which is exactly what I need.
This is correct. However, in your first post you accessed it via \(a_{i,s}\). In your second comment you seem to have corrected this so this clarifies the confusion.
5. If quicksum can only go through lists, it can't iterate through my multidicts..?:
From multidict documentation:
Return value:
A list, where the first member contains the shared key values, and the following members contain the dictionaries that result from splitting the value lists from the input dictionary.
This means that your scenarios and fares are lists, while capacities, scetime, probability,values,demand are dictionaries. Thus, your quicksums will work as intended for scenarios and fares (which is all you need). What did not work in your first post was the usage of parentheses.
(quicksum(x[f,t]) for f in fares for t in times[:t_last-1])
does not work, because \(\texttt{x[f,t]}\) itself cannot be accessed because there is no f and t in this context.
quicksum(x[f,t] for f in fares for t in times[:t_last-1])
works because \(\texttt{x[f,t] for f in fares for t in times[:t_last-1]}\) generates a list over 2 \(\texttt{for}\)-loops. To better understand the problem just try the following
print(x[f,t]) # will provide an error because f and t are not specified
print(x[f,t] for f in fares for t in times[:t_last-1]) # will print a list of x[f,t] entriesFor a better understanding, please refer to our Python examples. In particular, the diet.py example has a similar structure to your model.
Best regards,
Jaromił0 -
Post is closed for comments.
Comments
7 comments