src/drop.cpp
/**
 * This heuristic drops a market from the solution and tries to insert one of
 * the unvisited ones as long as it yields cost reduction while maintaining
 * feasibility.
 */
This heuristic drops a market from the solution and tries to insert one of
the unvisited ones as long as it yields cost reduction while maintaining
feasibility.
This heuristic drops a market from the solution and tries to insert one of the unvisited ones as long as it yields cost reduction while maintaining feasibility .
int exchange_heuristic(const TPP::Instance &instance, TPP::Solution &sol) {
    LOG_SCOPE_F(INFO, "exchange_heuristic");
    LOG_F(INFO, "Start cost: %d", sol.cost_);
    auto total_cost_change = 0;
    auto unselected = sol.get_unselected_markets();
    auto solution_changed = false;
    const vector<size_t> markets_to_check(sol.route_.begin() + 1, sol.route_.end());
    for (const auto market_id : markets_to_check) {
        const auto cost_before_removal = sol.cost_;
        const auto market_pos = sol.get_market_pos_in_route(market_id);
        sol.remove_market_at_pos(market_pos);
        bool found = false;
        for (auto cand : unselected) {
            if ( !sol.check_market_satisfies_demand(cand) ) {
                continue ;
            }
            const auto verdict = sol.calc_market_add_cost(cand);
            if (sol.cost_ + verdict.cost_change_ <= cost_before_removal
                    && verdict.demand_satisfied_) {
                LOG_F(INFO, "Cost of adding %zu is %d at pos %zu",
                        cand, verdict.cost_change_, verdict.index_);
                const auto prev_cost = sol.cost_;
                total_cost_change += verdict.cost_change_;
                sol.insert_market_at_pos(cand, verdict.index_);
                CHECK_F(prev_cost + verdict.cost_change_ == sol.cost_,
                        "Updated cost should be OK, %d", sol.cost_);
                LOG_F(INFO, "Cost now: %d", sol.cost_);
                unselected.erase(find(begin(unselected), end(unselected), cand));
                found = true;
                break ;
            }
        }
        if (!found) { 
            sol.insert_market_at_pos(market_id, market_pos);
        } else {
            solution_changed = true;
        }
    }
    if (solution_changed) {
        CHECK_F(is_solution_valid(instance, sol.route_),
                "Sol. should be valid");
    }
    return total_cost_change;
}
int exchange_heuristic ( const TPP :: Instance & instance , TPP :: Solution & sol ) { LOG_SCOPE_F ( INFO , " " ) ; LOG_F ( INFO , " " , sol . cost_ ) ; auto total_cost_change = 0 ; auto unselected = sol . get_unselected_markets ( ) ; auto solution_changed = false ; const vector < size_t > markets_to_check ( sol . route_ . begin ( ) + 1 , sol . route_ . end ( ) ) ; for ( const auto market_id : markets_to_check ) { const auto cost_before_removal = sol . cost_ ; const auto market_pos = sol . get_market_pos_in_route ( market_id ) ; sol . remove_market_at_pos ( market_pos ) ; bool found = false ; for ( auto cand : unselected ) { if ( ! sol . check_market_satisfies_demand ( cand ) ) { continue ; } const auto verdict = sol . calc_market_add_cost ( cand ) ; if ( sol . cost_ + verdict . cost_change_ <= cost_before_removal && verdict . demand_satisfied_ ) { LOG_F ( INFO , " " , cand , verdict . cost_change_ , verdict . index_ ) ; const auto prev_cost = sol . cost_ ; total_cost_change += verdict . cost_change_ ; sol . insert_market_at_pos ( cand , verdict . index_ ) ; CHECK_F ( prev_cost + verdict . cost_change_ == sol . cost_ , " " , sol . cost_ ) ; LOG_F ( INFO , " " , sol . cost_ ) ; unselected . erase ( find ( begin ( unselected ) , end ( unselected ) , cand ) ) ; found = true ; break ; } } if ( ! found ) { sol . insert_market_at_pos ( market_id , market_pos ) ; } else { solution_changed = true ; } } if ( solution_changed ) { CHECK_F ( is_solution_valid ( instance , sol . route_ ) , " " ) ; } return total_cost_change ; }
This heuristic drops a market from the solution and tries to insert one of
 the unvisited ones as long as it yields cost reduction while maintaining
 feasibility.
This heuristic drops a market from the solution and tries to insert one of the unvisited ones as long as it yields cost reduction while maintaining feasibility .
// Look for another market to insert // Restore solution to the previous state