[ML] Function approximation for "definitely bad" moves about euro-neurips-2022 HOT 10 CLOSED

@Y-Jansen I think this one is possibly more important than #44, if that turns out to be too hard. This should be fairly easy to try/make work fast.

from euro-neurips-2022.

I've put some raw data here [all instances, 10s runtime - although all the IO takes quite a while, so that 10s is not exact]. Each text file consists of size-line records, generated using the following code:

std::cout << idx << '\n';
std::cout << U->client << ' ' << V->client << ' ' << res << '\n';
std::cout << *U->route;
std::cout << *V->route;
std::cout << U->route->load() << ' ' << V->route->load() << '\n';
std::cout << U->route->timeWarp() << ' ' << V->route->timeWarp() << '\n';

The first line gives the operator index (from 0, for all node operators). The second line gives the U and V clients IDs, and the resulting value of the proposed operator swap (>= 0 is non-improving, < 0 is improving). And then two lines with the U and V routes. The next line gives the load on the routes of U and V. And then the final line the time warp on these routes.

Example:

0
133 19 -2071
Route #5: 331 242 113 162 168 370 227 350 152 252 409 392 64 406 284 16 133 137 210 405 114 30 340 358 50
Route #21: 49 165 316 190 272 19 277 231 342 288 287 45 39 156 154 93 420 336 200 23 416 77 124 310 330
171 151
60396 55886

This tested $(1, 0)$-Exchange on U = 133, V = 19, which is an improving move with delta cost -2071. The routes are given before they are changed (so these are the two routes as they were tested; inserting U after V has not yet been done). Before the change, the load on the route of U was 171, on the route of V 151. Finally, before the change, the time warp on the route of U was 60396, and on the route of V it was 55886.

The operators have the following indices/names:

0. $(1, 0)$-Exchange
1. $(2, 0)$-Exchange
2. $(2, 0)$-Reverse-Exchange
3. $(2, 2)$-Exchange
4. $(2, 1)$-Exchange
5. $(1, 1)$-Exchange
6. 2-OPT

from euro-neurips-2022.

I need to update the data and data description, but my laptop charger has died so that will have to wait a bit :-).

from euro-neurips-2022.

The link above now points to the new data.

from euro-neurips-2022.

Brief update on this. I have focused only on $(N, M)$-Exchange for now. Since that's 6 out of 8 operators, we should be OK. A simple logistic classifier seems to work really well already, even with just a few simple features (eight: 4 distances, and load/time feasibilities for each route).

In the figure above, 0 indicates that this move won't improve the solution, and 1 that it will. So about 80% of the useless moves are correctly classified as such, and 70% of the improving moves as well. If this result is robust after further cross-validation, we have a very good and fast classifier that will improve LS performance significantly.

I hope to finish final tweaking and cross-validation tomorrow.

from euro-neurips-2022.

I'm pivoting this to route operators. I finished a classifier for the $(N, M)$-Exchange moves, and it gets good performance in cross-validation, but actual real-world performance is rather disappointing (+20% iterations or so, but no better objectives). I suspect this is due to two things:

• Evaluating an $(N, M)$-Exchange move is already really fast, so evaluating a classifier instead of a full move is not that much faster.
• Missing a good move hurts a lot. So even if we get 'most' moves right, 70-80% correct classification on improving moves is not high enough.

It's probably easier to classify moves in route operators, since those are less proximity oriented than node operators (thus, hopefully, resulting in clearer distinctions between good and bad moves). I will start with RELOCATE*, and see how that works out.

from euro-neurips-2022.

Drop-in replacement for applyRouteOperators that collects route-based data:

bool LocalSearch::applyRouteOperators(Route *U, Route *V)
{
    for (size_t idx = 0; idx != routeOps.size(); ++idx)
    {
        auto op = routeOps[idx];
        auto const res = op->evaluate(U, V);

        std::cout << idx << ' ' << res << '\n';
        std::cout << *U;
        std::cout << *V;
        std::cout << U->load() << ' ' << V->load() << '\n';
        std::cout << U->timeWarp() << ' ' << V->timeWarp() << '\n';

        if (res < 0)
        {
            op->apply(U, V);
            update(U, V);

            std::cout << *U;
            std::cout << *V;
            std::cout << U->load() << ' ' << V->load() << '\n';
            std::cout << U->timeWarp() << ' ' << V->timeWarp() << '\n';
            
            return true;
        }
    }

    return false;
}

from euro-neurips-2022.

In #81 I've tried a lot of stuff to make this work, first for node ops (not worth it) and then for route ops. The classifier for route ops seems to get roughly similar performance as the current mechanism with an intensification probability, so it appears to be reasonably effective.

But.. not having route operators at all is also effective. So why bother? We're better off with simpler node operators.

from euro-neurips-2022.

Some remarks that may be interesting for future research:

• Do we have enough relevant data? We now use only 1 second of runtime data. This means that we are primarily learning on the space of 2-5% gap solutions. But we are missing data in the space of near-optimal solutions with say 0-2% gap.
• Are there enough features? The node features include nodes delta cost and route infeasibilities. But how about node time windows?

I think this is interesting research to continue after the competition. :-)

from euro-neurips-2022.

I've uploaded a new version of the dataset linked to above. This one's about the route operators, and is basically the raw data I've used in my route notebook.

Do we have enough relevant data? We now use only 1 second of runtime data. This means that we are primarily learning on the space of 2-5% gap solutions. But we are missing data in the space of near-optimal solutions with say 0-2% gap.

For routes it's 10s, and that gets us around 100K observations (of which 2-300 are improving moves). Not sure if that's enough, but it is definitely quite a lot already.

Are there enough features? The node features include nodes delta cost and route infeasibilities. But how about node time windows?

I tried a feature that was basically <size of node time window> / <total time range> (so normalised to [0, 1]), but the classifier did not seem to get a lot out of that (coefficients were very small). But there's definitely room for further improvement here!

from euro-neurips-2022.