Column Generation for Mix Passenger Flow
進行中In our code, the outcome provides 3 iterations in which the last one the objective function increases. This shouldn't happen, could you perhaps explain what I can do to solve this?
-
Hi Julia,
If the problem is a minimization problem and all you do between iterations is adding a column, this should not happen indeed, since the optimal solution from the previous iteration is still a feasible one. Could you share the relevant parts of your Python code here, e.g. the part where you modify and re-run your (master) problem?
Kind regards,
Ronald0 -
def solve_pricing_problem(p_id, duals, F_dict, I_dict, R_dict,alternative_itinerary):
pi = {}
sigma = {}
for name, val in duals.items():
if "capacity_constraint_" in name:
flight_id = name.replace("capacity_constraint_", "")
pi[flight_id] = val
elif "allocation_constraint_" in name:
it_id = name.replace("allocation_constraint_", "")
sigma[it_id] = val
sigma_p = sigma.get(p_id, 0.0)
It_p = I_dict[p_id]
flights_p = [It_p.Flight1] if pd.isna(It_p.Flight2) else [It_p.Flight1, It_p.Flight2]
fare_p = It_p.price
# sum_pi_p = sum(pi.get(f, 0.0) for f in flights_p)
slack_r ={}
Bpr = {(recapture.FromI, recapture.ToI): recapture.RR for recapture in R_dict.values()}
FareP = {itinerary.id: itinerary.price for itinerary in I_dict.values()}
for r in alternative_itinerary:
if r != 0:
It_r = I_dict.get(r, None)
if It_r is None or It_r.price is None:
print(f"Skipping itinerary {r} due to missing price.")
continue
flights_r = [It_r.Flight1] if pd.isna(It_r.Flight2) else [It_r.Flight1, It_r.Flight2]
slack_r[r] = (
fare_p - sum(pi.get(p) or 0 for p in flights_p)
- Bpr.get((p_id, r), 0.0) * (FareP[r] - sum(pi.get(f, 0.0) for f in flights_r))
- sigma_p
)
column_additions = []
for it in slack_r.keys():
if slack_r[it] < 0:
# print(f"Adding column for itinerary {it} with reduced cost {slack_r[it]}")
column_additions.append(it)
# for name, val in slack_r.items():
# if val < 0:
# print(f"Reduced Costs for Itineraries: {slack_r}")
return column_additions
# =========================================================================================================================
# Column Generation Loop
# =========================================================================================================================
def column_loop(adv, model, tpr_vars, F_dict, I_dict, R_dict):
improvement = True
iteration = 0
while improvement:
iteration += 1
print(f"\nIteration {iteration}")
duals = extract_dual_values(model)
objective_values.append({"iteration": iteration, "objective": model.objVal})
iteration_log.append(iteration)
new_it_found = False
new_it = []
idv = list(set(I_dict.keys()) - set(adv))
for p in I_dict.keys():
if p != 0:
it = solve_pricing_problem(p, duals, F_dict, I_dict, R_dict, alternative_itinerary=idv)
if len(it) > 0:
new_it = new_it + it
unique_new_it = list(set(new_it))
if len(unique_new_it) > 0:
new_it_found = True
print(adv)
print(unique_new_it)
if new_it_found:
adv = adv + unique_new_it
model, tpr = build_RMP(F_dict,I_dict,R_dict,active_decision_variables=adv, iteration=iteration)
model.optimize()
# add new it to adv
improvement = True
else:
print("No improving columns found. Column generation converged.")
improvement = FalseI think these are the relevant parts. We are indeed having a minimization problem so it is strange. This is our output: [{'iteration': 1, 'objective': 1756776.0}, {'iteration': 2, 'objective': 1707993.0}, {'iteration': 3, 'objective': 1710775.9646153848}, {'iteration': 4, 'objective': 1710807.2646153846}, {'iteration': 5, 'objective': 1711846.0646153847}]
0 -
Hi,
My first guess would be that there is a problem with build_RMP. I believe you're constructing a completely new model in each iteration, which could be a bit slow and makes it a bit harder to compare differences between models in consecutive iterations. Have you tried keeping a single model, and updating it iteratively (e.g. add variable, put it in the right constraints, set its objective coefficient)?
Alternatively, you could (a) store the optimal solution from iteration 3 in Python (b) in the model for iteration 4, fix the value of all variables by setting their LB and UB to the values you stored (c) let Gurobi optimize and check the solution status. If the model is infeasible, somehow part of the feasible space has been removed in iteration 4 which needs debugging.
Kind regards,
Ronald0 -
Thanks Ronald for your answer!
In the end, the issue was with the capacity constraint. But it works now, so thank you again!0 -
Ronald van der Velden I just stumbled upon this post. I am a bit confused right now. How can i add a variable if the model has already been fixed? Suppose i have my master problem and initialize it with the variables \(\lambda_1 - \lambda_{200}\). How can i now add the 201th? Do i need to re-initialize the model?
0
サインインしてコメントを残してください。
コメント
5件のコメント