import itertools

import gurobipy as gp
from time import perf_counter
from gurobipy import GRB
from src.busopt.config import ModelConfig
from src.entity.network_entity import OD_demand
from src.entity.solution_entity import *
from src.algos.transit_assignment import transit_assignment_gp
from src.algos.acceleration import Outer_bounding_prob


def _compute_outer_objective(config: ModelConfig, line_list, cur_mid_sol, cur_low_sol, *, include_operating_cost: bool = True):
    user_cost = config.vot * (sum(value[0] * value[1] for value in cur_low_sol.v_sol.values()) + sum(cur_low_sol.t_sol.values()))
    oper_cost = sum(2 * config.c_bar * l.length * cur_mid_sol.f_sol[l.line_id] for l in line_list) if include_operating_cost else 0.0
    subsidies = 0
    for l in line_list:
        total_flow_mile = sum(tl.flow * tl.length for r in l.routes.values() for tl in r.transit_links)
        private_portion = (l.freq - l.org_freq) / l.freq
        subsidies += total_flow_mile * config.s_bar * private_portion

    return {"Q_op": user_cost + oper_cost + subsidies * config.mu,
            "user_cost": user_cost,
            "oper_cost": oper_cost,
            "subsidies": subsidies}


def _apply_mid_solution_to_network(line_list, mid_sol):
    for l in line_list:
        l.freq = mid_sol.f_sol[l.line_id] + l.org_freq
        for route in l.routes.values():
            for board_link in route.board_links:
                board_link.freq = mid_sol.f_sol[l.line_id] + l.org_freq


def _build_low_solution(hypergraph):
    return LowSolution(
        v_dict={a.link_id: (float(a.flow), float(a.travel_cost)) for a in hypergraph.link_dict.values()},
        t_dict={i.node_id: i.wait for i in hypergraph.node_dict.values()},
    )


def evaluate_fixed_solution(hypergraph, line_list, demand_list, config: ModelConfig, fixed_x_sol, fixed_f_sol):
    fixed_up_solution = UpSolution(x_dict=fixed_x_sol)
    fixed_mid_sol = MidSolution(f_dict=fixed_f_sol)
    _apply_mid_solution_to_network(line_list, fixed_mid_sol)
    transit_assignment_gp(hypergraph, demand_list, enable_logging=False)
    fixed_low_sol = _build_low_solution(hypergraph)
    dict_subprob = _compute_outer_objective(config, line_list, fixed_mid_sol, fixed_low_sol)
    q_op = dict_subprob["Q_op"]
    return {
        "iterations": 1,
        "max_iteration_step": 1,
        "x-f_iterations": 1,
        "max_f_iterations": 1,
        "CPU (s)": 0.0,
        "upper_bound": q_op,
        "lower_bound": q_op,
        "Gap": 0.0,
        "relaxed_activation": 0,
        "iteration_find_best": 1,
        "time_find_best": 0.0,
        "optimal_obj_user_cost": dict_subprob["user_cost"],
        "optimal_obj_mid_oper": dict_subprob["oper_cost"],
        "optimal_obj_funding": dict_subprob["subsidies"],
        "optimal_mid_revenue": 0.0,
        "optimal_up_solution": fixed_up_solution.x_sol,
        "optimal_mid_solution": fixed_mid_sol.f_sol,
        "optimal_low_solution": fixed_low_sol.v_sol,
        "fixed_upper_solution": fixed_up_solution.x_sol,
        "inner_problem": None,
        "config": config.to_dict(),
    }


def solve_with_fixed_upper_solution(
    hypergraph,
    line_list,
    demand_list,
    config: ModelConfig,
    fixed_x_sol,
    *,
    enforce_min_freq_when_selected: bool = True,
    require_positive_profit: bool = True,
    include_operating_cost: bool = True,
):
    fixed_up_solution = UpSolution(x_dict=fixed_x_sol)
    inner_model = Inner_relaxed_mp(
        hypergraph,
        line_list,
        demand_list,
        fixed_up_solution,
        config,
        enforce_min_freq_when_selected=enforce_min_freq_when_selected,
        require_positive_profit=require_positive_profit,
    )
    is_feasible, best_mid_sol, best_low_sol, _, inner_iter = inner_model.solve()

    result = {
        "iterations": 1,
        "max_iteration_step": 1,
        "x-f_iterations": inner_iter,
        "max_f_iterations": inner_model.output_info["max_iteration_step"],
        "CPU (s)": inner_model.output_info["CPU (s)"],
        "upper_bound": None,
        "lower_bound": None,
        "Gap": 100.0,
        "relaxed_activation": 0,
        "iteration_find_best": None,
        "time_find_best": None,
        "optimal_obj_user_cost": None,
        "optimal_obj_mid_oper": None,
        "optimal_obj_funding": None,
        "optimal_mid_revenue": inner_model.output_info["optimal_obj_value"],
        "optimal_up_solution": fixed_up_solution.x_sol,
        "optimal_mid_solution": None,
        "optimal_low_solution": None,
        "inner_problem": dict(inner_model.output_info),
        "fixed_upper_solution": fixed_up_solution.x_sol,
        "config": config.to_dict()
    }

    if not is_feasible:
        return result

    dict_subprob = _compute_outer_objective(
        config,
        line_list,
        best_mid_sol,
        best_low_sol,
        include_operating_cost=include_operating_cost,
    )
    q_op = dict_subprob["Q_op"]
    result.update({
        "upper_bound": q_op,
        "lower_bound": q_op,
        "Gap": 0.0,
        "iteration_find_best": 1,
        "time_find_best": inner_model.output_info["CPU (s)"],
        "optimal_obj_user_cost": dict_subprob["user_cost"],
        "optimal_obj_mid_oper": dict_subprob["oper_cost"],
        "optimal_obj_funding": dict_subprob["subsidies"],
        "optimal_mid_solution": best_mid_sol.f_sol,
        "optimal_low_solution": best_low_sol.v_sol
    })
    return result


# noinspection PyShadowingNames
class Inner_relaxed_mp:

    def __init__(
        self,
        hypergraph,
        line_list,
        demand_list,
        fixed_up_solution,
        config: ModelConfig,
        *,
        enforce_min_freq_when_selected: bool = True,
        require_positive_profit: bool = True,
    ):
        self.config = config
        self.enforce_min_freq_when_selected = enforce_min_freq_when_selected
        self.require_positive_profit = require_positive_profit
        fixed_x = fixed_up_solution.x_sol
        demand_dict = OD_demand.destination_based_OD(demand_list)
        model = gp.Model("Inner_relaxed_mp_model")
        model.setParam("OutputFlag", 0)

        """
        Create Gurobi model.
        """

        # Variables.
        l_indices = [l.line_id for l in line_list]
        f_l = model.addVars(l_indices, vtype=GRB.CONTINUOUS, name='f_l')
        y_ln = model.addVars(l_indices, config.freq_set, vtype=GRB.BINARY, name='y_ln')
        z_ip = model.addVar(vtype=GRB.CONTINUOUS, name='z_ip', ub=1e7)  # Benders auxiliary variable


        # Constraints.
        # constraints that links f_l and y_ln:
        model.addConstrs(f_l[l.line_id] == gp.quicksum(n * y_ln[l.line_id, n] for n in config.freq_set) for l in line_list)
        model.addConstrs(gp.quicksum(y_ln[l.line_id, n] for n in config.freq_set) == 1.0 for l in line_list)

        # f_l - pN * x_l <= 0
        cons_1 = model.addConstrs(f_l[l_index] - config.freq_set[-1] * fixed_x[l_index] <= 0 for l_index in l_indices)

        # f_l - p1 * x_l >= 0
        cons_2 = (
            model.addConstrs(f_l[l_index] - config.freq_set[1] * fixed_x[l_index] >= 0 for l_index in l_indices)
            if enforce_min_freq_when_selected
            else None
        )


        # Objectives.
        obj_mp_part = gp.quicksum(2 * config.c_bar * l.length * f_l[l.line_id] for l in line_list)
        obj_func = z_ip - obj_mp_part
        model.setObjective(obj_func, GRB.MAXIMIZE)
        model.update()

        # register class variable
        self.model = model
        self.line_list = line_list
        self.fixed_up_solution = fixed_up_solution
        self.hypergraph = hypergraph
        self.demand_list = demand_list
        self.demand_dict = demand_dict
        self.f_l = f_l
        self.y_ln = y_ln
        self.obj_mp_part = obj_mp_part
        self.z_ip = z_ip
        self.cons_1 = cons_1
        self.cons_2 = cons_2
        self.Benders_opt_cut = []
        self.Benders_fea_cut = []
        self.subgradient_cut = []
        self.output_info = {}

    def update_fixed_up_solution(self, new_up_solution):
        self.fixed_up_solution = new_up_solution
        fixed_x = self.fixed_up_solution.x_sol
        for l in self.line_list:
            self.cons_1[l.line_id].rhs = self.config.freq_set[-1] * fixed_x[l.line_id]
            if self.cons_2 is not None:
                self.cons_2[l.line_id].rhs = self.config.freq_set[1] * fixed_x[l.line_id] - 1e-4
        self.model.update()

    def update_freq(self, mid_sol):
        _apply_mid_solution_to_network(self.line_list, mid_sol)

    def clear_benders_cut(self):
        self.model.remove(self.Benders_opt_cut)
        self.model.remove(self.Benders_fea_cut)
        self.model.update()
        self.Benders_opt_cut = []
        self.Benders_fea_cut = []

    def clear_subgradient_cut(self):
        self.model.remove(self.subgradient_cut)
        self.model.update()
        self.subgradient_cut = []

    def _compute_subprob_ub(self):
        """
        Calculates the subproblem's upper bound for Benders Optimality Cut. U_ip
        Assume that company set maximum frequency for each line;
        this results in maximum profit for the company (UB)
        """
        maximum_freq = [self.config.freq_set[-1] if round(self.fixed_up_solution.x_sol[l.line_id]) == 1 else 0 for l in self.line_list]
        used_mid_sol = MidSolution(f_dict=dict(zip(self.f_l.keys(), maximum_freq)))  # 取最大的f，暂时忽略车队规模约束

        # Solve transit assignment problem
        # update link frequencies
        self.update_freq(used_mid_sol)
        transit_assignment_gp(self.hypergraph, self.demand_list, enable_logging=False)

        # Compute objective function Q_ip(f)
        return self._compute_subprob_obj()

    def _compute_subprob_obj(self):
        """
        Calculates the subproblem's objective function value. Q_ip(f)
        """
        Q_ip = 0
        for l in self.line_list:
            total_flow_mile = sum([tl.flow * tl.length for r in l.routes.values() for tl in r.transit_links])
            private_portion = (l.freq - l.org_freq) / l.freq
            Q_ip += total_flow_mile * (self.config.tau + self.config.s_bar) * private_portion

        return Q_ip

    def solve(self):
        UB = float("inf")  # upper bound
        LB = -float("inf")  # lower bound
        iter_step = 0  # iteration step counter
        best_mid_sol, best_low_sol = None, None
        epsilon = 1e-3  # optimality gap
        U_ip = self._compute_subprob_ub()  # get the subproblem's upper bound
        z_bound_constr = self.model.addConstr(self.z_ip <= U_ip)

        start_time = perf_counter()
        is_feasible = True
        print(f"subproblem upper bound: {U_ip}")
        while True:
            iter_step += 1
            self.model.optimize()

            if self.model.status == GRB.Status.INFEASIBLE or self.model.status == GRB.Status.UNBOUNDED:
                print(f"Inner relaxed MP: Iteration {iter_step}, Status: {self.model.status}")
                is_feasible = False
                break

            # update upper bound and solution
            UB = min(UB, self.model.objVal)
            this_mid_sol = MidSolution(f_dict={key: value.X for key, value in self.f_l.items()})
            self.update_freq(this_mid_sol)

            # solve the resulting transit assignment problem.
            transit_assignment_gp(self.hypergraph, self.demand_list, enable_logging=False)

            # Calculate Q_ip(f) and update lower bound
            Q_ip = self._compute_subprob_obj()
            this_obj_mp_part = self.obj_mp_part.getValue()
            if Q_ip - this_obj_mp_part > LB:
                LB = Q_ip - this_obj_mp_part
                best_mid_sol = this_mid_sol
                best_low_sol = _build_low_solution(self.hypergraph)

            # Print iterative information
            if iter_step == 2 or iter_step % 50 == 0:
                print(f"Iteration {iter_step}, "
                      f"LB = {LB:.2f}, UB = {UB:.2f}, Gap = {(UB - LB) * 100 / abs(UB) if UB != 0 else 100:.2f}%, "
                      f"Elapsed time: {perf_counter() - start_time:.2f} secs")

            if UB - LB < epsilon:
                print(f"Inner relaxed MP: Iteration {iter_step}, Converged! obj = {LB}")
                break

            """
            add benders cut to the master problem
            if the subproblem returns an optimal solution, optimality cut is added:
                z_ip <= - (U_ip - Q_ip(f)) * expr + Q_ip(f)
                expr = sum_{1-set}y_ln - sum_{0-set}y_ln - len(l_set)
            elseif subproblem is infeasible, feasibility cut is added:
                expr + 1 <= 0
            """
            expr = 0
            for l in self.line_list:
                for n in self.config.freq_set:
                    if abs(self.y_ln[l.line_id, n].X - 1.0) < 1e-5:
                        expr += self.y_ln[l.line_id, n]
                    elif abs(self.y_ln[l.line_id, n].X) < 1e-5:
                        expr += - self.y_ln[l.line_id, n]
            expr -= len(self.line_list)

            is_subprob_feasible = (Q_ip - this_obj_mp_part >= self.config.Psi0) or not self.require_positive_profit
            if is_subprob_feasible:
                self.Benders_opt_cut.append(self.model.addConstr(self.z_ip <= (Q_ip - U_ip) * expr + Q_ip))
            else:
                self.Benders_fea_cut.append(self.model.addConstr(expr + 1.0 <= 0))
            self.model.update()

        if self.require_positive_profit and LB + 1e-5 <= self.config.Psi0:
            is_feasible, best_mid_sol, best_low_sol, LB = False, None, None, -float("inf")

        end_time = perf_counter()
        flex_x_num = int(sum(self.fixed_up_solution.x_sol.values()))
        maximum_step = (len(self.config.freq_set) - 1) ** flex_x_num
        print(f"Inner Problem time elapsed: {end_time - start_time:.2f} s")
        print(f"Inner Problem convergence iteration: {iter_step - 1}/{maximum_step}, efficiency: {(iter_step - 1) / maximum_step}")

        self.output_info.update({
            "iteration_step": iter_step - 1,
            "max_iteration_step": maximum_step,
            "CPU (s)": end_time - start_time,
            "optimal_obj_value": LB,
            "optimal_mid_solution": best_mid_sol.f_sol if is_feasible else None,
            "optimal_low_solution": best_low_sol.v_sol if is_feasible else None,
            "Gap": ((UB - LB) * 100 / abs(UB) if UB != 0 else 100) if is_feasible else 100,
            "U_ip": U_ip
        })

        self.model.remove(z_bound_constr)
        self.model.update()

        return is_feasible, best_mid_sol, best_low_sol, LB, iter_step - 1


# noinspection PyShadowingNames
class Outer_relaxed_mp:
    def __init__(
        self,
        hypergraph,
        line_list,
        demand_list,
        config: ModelConfig,
        *,
        include_operating_cost: bool = True,
    ):
        self.config = config
        self.include_operating_cost = include_operating_cost
        model = gp.Model("Outer_relaxed_mp_model")
        model.setParam("OutputFlag", 0)

        """
        Create Gurobi model.
        """

        # Variables.
        l_indices = [l.line_id for l in line_list]
        x_l = model.addVars(l_indices, vtype=GRB.BINARY, name='x_l')
        z_op = model.addVar(vtype=GRB.CONTINUOUS, name='z_op', lb=0)  # Benders auxiliary variable

        # Objectives.
        model.setObjective(z_op, GRB.MINIMIZE)
        model.update()

        # register class variable
        self.model = model
        self.hypergraph = hypergraph
        self.line_list = line_list
        self.demand_list = demand_list
        self.x_l = x_l
        self.z_op = z_op
        self.output_info = {}


    def _compute_subprob_obj(self, cur_mid_sol, cur_low_sol):
        """
        Calculates the subproblem's objective function value. Q_op(x)
        """
        return _compute_outer_objective(
            self.config,
            self.line_list,
            cur_mid_sol,
            cur_low_sol,
            include_operating_cost=self.include_operating_cost,
        )


    def solve(self):
        UB = float("inf")  # upper bound
        LB = -float("inf")  # lower bound
        iter_step = 0  # iteration step counter
        best_up_sol, best_mid_sol, best_low_sol = None, None, None
        best_user_cost, best_mid_oper, best_funding = None, None, None
        best_sol_iter, best_sol_time = None, None
        inner_model = None
        best_mid_revenue = None
        solution_set = []
        count_up_mid_comb = 0
        count_relax_active = 0
        abort = False
        self.output_info['iteration_details'] = []

        # find L_op (enumerate all up solutions, and solve relaxed subproblem for each)
        d_relaxed_subprob = {}
        print(f"Computing lower bound for O-BLP subproblem")
        start_time_lb = perf_counter()
        d_relax_bound = {}
        for i, comb in enumerate(itertools.product([0, 1], repeat=len(self.x_l))):
            up_sol = UpSolution(x_dict={k: v for k, v in zip(self.x_l, comb)})
            rs = Outer_bounding_prob(self.hypergraph, self.line_list, self.demand_list, up_sol)
            d_relaxed_subprob[comb] = rs
            relax_bound = sum(rs.solve().values())
            d_relax_bound[comb] = relax_bound
            print(f"iter: {i}, cost time: {perf_counter()-start_time_lb:.2f}")
        L_op = min(d_relax_bound.values())
        print(f"Compute lower bound for O-BLP subproblem {L_op:.2f}, costs {perf_counter() - start_time_lb:.2f} secs\n")
        self.model.addConstr(self.z_op >= L_op)

        start_time = perf_counter()
        while True:
            iter_step += 1
            print(f"========================== O-BLP Master Problem: Iteration {iter_step} =================================")
            print(f"Start optimizing")
            self.model.optimize()

            if self.model.status == GRB.Status.INFEASIBLE or self.model.status == GRB.Status.UNBOUNDED:
                print(f"O-BLP Master Problem: Iteration {iter_step}, Status: {self.model.status}")
                break

            # update lower bound and solution
            LB = max(LB, self.model.objVal)
            this_up_sol = UpSolution(x_dict={key: value.X for key, value in self.x_l.items()})
            print(f"\nSolving master problem...")
            print(f"Up solution in this iteration: {this_up_sol} | Master problem Obj.value: {self.model.objVal:.2f}")

            # Termination Criteria: reach a solution once acquired
            if this_up_sol in solution_set:
                print(f"reach a solution once acquired")
                print(f"O-BLP Master Problem:  Iteration {iter_step}, Converged!")
                break
            else:
                solution_set.append(this_up_sol)

            trigger_inner_model = True
            this_mid_sol, Q_op, this_user_cost, this_oper_cost, this_subsidies = None, None, None, None, None
            relaxed_prob_obj_value = None

            # before solving the subproblem, derive a LB by solving a series of relaxed problem
            if self.config.accelerate:
                print(f"\nSolving relaxed subproblem...")
                start_time_r = perf_counter()
                r = d_relaxed_subprob[tuple([round(v, 1) for v in this_up_sol.x_sol.values()])].solve()
                min_user_cost = r['v1']
                min_oper_cost = r['v2']
                min_funding_cost = r['v3']
                end_time_r = perf_counter()
                relaxed_prob_obj_value = min_user_cost + min_oper_cost + min_funding_cost
                print(f"Relaxed subproblem elapsed time: {end_time_r - start_time_r:.2f} secs")
                print(f"Relaxed subproblem Obj.value: {relaxed_prob_obj_value:.2f} "
                      f"(min_user_cost: {min_user_cost:.2f} | "
                      f"min_oper_cost: {min_oper_cost:.2f} | "
                      f"min_funding_cost:{min_funding_cost:.2f})")

                if relaxed_prob_obj_value >= UB:
                    trigger_inner_model = False
                    count_relax_active += 1
                    # add feasibility cut to exclude the current solution
                    expr = 0
                    length_1set = 0
                    for l in self.line_list:
                        if abs(self.x_l[l.line_id].X - 1.0) < 1e-5:
                            expr += self.x_l[l.line_id]
                            length_1set += 1
                        elif abs(self.x_l[l.line_id].X) < 1e-5:
                            expr -= self.x_l[l.line_id]
                    expr -= length_1set

                    self.model.addConstr(expr + 1.0 <= 0)
                    self.model.update()

                    # Print iterative information
                    print(f"\n[SUMMARY]")
                    print(f"Relaxed subproblem's objVal is greater than global UB ({relaxed_prob_obj_value:.2f} > {UB:.2f}), skip IBLP")
                    print(f"Best incumbent solution: {best_up_sol}, {best_mid_sol}")
                    print(f"LB = {LB:.2f}, UB = {UB:.2f}, Gap = {(UB - LB) * 100 / abs(UB) if UB != 0 else 100:.2f}%")

            if trigger_inner_model:
                # solve the subproblem to optimal
                print(f"\nSolving subproblem...")
                if inner_model is None:
                    inner_model = Inner_relaxed_mp(self.hypergraph, self.line_list, self.demand_list, this_up_sol, self.config)
                    inner_model.update_fixed_up_solution(this_up_sol)
                else:
                    inner_model.update_fixed_up_solution(this_up_sol)
                    inner_model.clear_benders_cut()
                    inner_model.clear_subgradient_cut()
                is_inner_feasible, this_mid_sol, this_low_sol, _, inner_iter = inner_model.solve()
                count_up_mid_comb += inner_iter

                """
                add benders cut to the master problem
                if the subproblem returns an optimal solution, optimality cut is added:
                    z_ip >= (gamma(x) - L_op) * expr + gamma(x)
                    expr = sum_{1-set}x_l - sum_{0-set}x_l - len({1-set}})
                elseif subproblem is infeasible, feasibility cut is added:
                    expr + 1 <= 0
                """
                expr = 0
                length_1set = 0
                for l in self.line_list:
                    if abs(self.x_l[l.line_id].X - 1.0) < 1e-5:
                        expr += self.x_l[l.line_id]
                        length_1set += 1
                    elif abs(self.x_l[l.line_id].X) < 1e-5:
                        expr -= self.x_l[l.line_id]
                expr -= length_1set

                if not is_inner_feasible:
                    # feasibility cut
                    self.model.addConstr(expr + 1.0 <= 0)
                    self.model.update()

                    # Print iterative information
                    print(f"\n[SUMMARY]")
                    print(f"Subproblem is infeasible, add a feasibility cut")
                    print(f"Best incumbent solution: {best_up_sol}, {best_mid_sol}")
                    print(f"LB = {LB:.2f}, UB = {UB:.2f}, Gap = {(UB - LB) * 100 / abs(UB) if UB != 0 else 100:.2f}% ")

                else:
                    # calculate Q_op(x) and update upper bound
                    dict_subprob = self._compute_subprob_obj(this_mid_sol, this_low_sol)
                    Q_op, this_user_cost, this_oper_cost, this_subsidies = (
                        dict_subprob["Q_op"], dict_subprob["user_cost"], dict_subprob["oper_cost"], dict_subprob["subsidies"])


                    if UB > Q_op:
                        UB = Q_op
                        best_up_sol = this_up_sol
                        best_mid_sol = this_mid_sol
                        best_low_sol = this_low_sol
                        best_user_cost = this_user_cost
                        best_mid_oper = this_oper_cost
                        best_funding = this_subsidies
                        best_mid_revenue = inner_model.output_info["optimal_obj_value"]
                        best_sol_iter = iter_step
                        best_sol_time = perf_counter() - start_time

                    # optimality cut
                    self.model.addConstr(self.z_op >= (Q_op - L_op) * expr + Q_op)

                    # Print iterative information
                    print(f"\n[SUMMARY]")
                    print(f"New incumbent: {this_up_sol == best_up_sol}")
                    print(f"This iteration solution: {this_up_sol}, {this_mid_sol}")
                    print(f"Best incumbent solution: {best_up_sol}, {best_mid_sol}")
                    print(f"objective value (total cost): {Q_op:.2f}")
                    print(f"passenger cost: {this_user_cost:.2f}, operating cost: {this_oper_cost:.2f}, funding (not cost): {this_subsidies:.2f}")
                    print(f"LB = {LB:.2f}, UB = {UB:.2f}, Gap = {(UB - LB) * 100 / abs(UB) if UB != 0 else 100:.2f}%")

            cum_time = perf_counter() - start_time
            print(f"Cumulative elapsed time: {cum_time:.2f} secs")
            print(f"====================================================================================================\n")

            self.output_info['iteration_details'].append({
                "iter_step": iter_step,
                "objective_value": Q_op, "passenger cost": this_user_cost, "operating cost": this_oper_cost, "funding": this_subsidies,
                "lb": LB, "ub": UB, "gap": (UB - LB) * 100 / abs(UB) if UB != 0 else 100,
                "relax_activate": not trigger_inner_model,
                "relax_bound": relaxed_prob_obj_value,
                "cumulative_elapsed_time": cum_time,
                "new_incumbent": this_up_sol == best_up_sol if best_up_sol is not None else None,
                "this_up_sol": this_up_sol.x_sol if this_up_sol is not None else None,
                "this_mid_sol": this_mid_sol.f_sol if this_mid_sol is not None else None,
                "best_up_sol": best_up_sol.x_sol if best_up_sol is not None else None,
                "best_mid_sol": best_mid_sol.f_sol if best_mid_sol is not None else None
            })


            if all(abs(value - 1.0) < 1e-5 for value in this_up_sol.x_sol.values()):
                self.output_info["largest_inner_info"] = inner_model.output_info.copy()

            if cum_time > self.config.time_limit:
                print(f"Exceed time limit, abort iteration!")
                abort = True
                break

        elapsed_time = self.config.time_limit if abort else perf_counter() - start_time
        iterations = iter_step if abort else iter_step - 1
        maximum_step = 2 ** len(self.line_list)

        # Optimization summary
        print(f"\n\n ============================ O-BLP Optimization Summary ============================")
        print(f"Time Elapsed: {elapsed_time:.2f} secs")
        print(f"Convergence Iteration: {iterations}/{maximum_step}, Efficiency: {iterations / maximum_step}")
        print(f"x-f expr Iteration: {count_up_mid_comb} / {len(self.config.freq_set) ** self.config.route_num}")
        print(f"Best solution: {best_up_sol}, {best_mid_sol}")
        print(f"Best objective value (total cost): {UB}")
        print(f"Best solution found at iteration {best_sol_iter}")
        print(f"Best solution found cost: {best_sol_time} secs")
        print(f"Relative gap: {(UB - LB) * 100 / abs(UB) if UB != 0 else 100:.2f}%")
        print(f"passenger cost: {best_user_cost}, operating cost: {best_mid_oper}, funding (not cost): {best_funding}")
        print(f"Count relaxed subproblem activation: {count_relax_active}")

        # Save results
        self.output_info.update({
            "iterations": iterations,
            "max_iteration_step": maximum_step,
            "x-f_iterations": count_up_mid_comb,
            "max_f_iterations": len(self.config.freq_set) ** self.config.route_num,
            "CPU (s)": elapsed_time,
            "upper_bound": UB,
            "lower_bound": LB,
            "Gap": (UB - LB) * 100 / abs(UB) if UB != 0 else 100,
            "relaxed_activation": count_relax_active,
            "iteration_find_best": best_sol_iter,
            "time_find_best": best_sol_time,
            "optimal_obj_user_cost": best_user_cost,
            "optimal_obj_mid_oper": best_mid_oper,
            "optimal_obj_funding": best_funding,
            "optimal_mid_revenue": best_mid_revenue,
            "optimal_up_solution": best_up_sol.x_sol if best_up_sol is not None else None,
            "optimal_mid_solution": best_mid_sol.f_sol if best_mid_sol is not None else None,
            "optimal_low_solution": best_low_sol.v_sol if best_low_sol is not None else None,
            "L_op": L_op,
            "config": self.config.to_dict()
        })



