メインコンテンツへスキップ

Column Generation for Mix Passenger Flow

進行中

コメント

5件のコメント

  • Ronald van der Velden
    Gurobi Staff Gurobi Staff

    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,
    Ronald

    0
  • Julia Huigen
    First Comment
    First Question
    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 = False


     

    I 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
  • Ronald van der Velden
    Gurobi Staff Gurobi Staff

    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,
    Ronald

    0
  • Julia Huigen
    First Comment
    First Question

    Thanks Ronald for your answer! 
    In the end, the issue was with the capacity constraint. But it works now, so thank you again!

    0
  • Carl Baier
    Thought Leader
    First Question

    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

サインインしてコメントを残してください。