Metaheuristics with RKO

What RKO is

The Random-Key Optimizer (RKO) is a Python package, rko, that comes installed on every Harumi compute kernel. It needs no license.

RKO searches a vector of random numbers between 0 and 1. You don't write a search algorithm. You write two functions:

• a decoder that turns those numbers into a solution of your problem (for example, sorting them to get an order of jobs);
• a cost that scores that solution. RKO minimizes it, so return the negated value if you want to maximize.

RKO then runs up to eight metaheuristics at once (BRKGA, multi-start, simulated annealing, VNS, ILS, LNS, PSO and GA), in parallel, sharing their best solutions.

When to use it

RKO fits when:

• the problem is combinatorial and large (hundreds to thousands of items), and an exact model in Gurobi or OR-Tools takes too long or has no tight formulation;
• a solution is naturally an order, a priority list, or a set of scores (sequencing, packing, routing, assignment by priority);
• the objective can only be computed by simulating the solution.

It does not fit when you need a proven optimal solution or an optimality gap. RKO gives neither: its result is always a heuristic one. For a problem an exact solver can finish, use the exact solver.

Run it in a project

[run]
command = "python main.py"
kernel = "or_python_medium"

import json
import os

import numpy as np
from rko import RKO


class SequencingEnv:
    """Order jobs on one machine to minimize total tardiness."""

    def __init__(self, durations, due_dates):
        self.durations = np.asarray(durations, dtype=float)
        self.due_dates = np.asarray(due_dates, dtype=float)

        # Required attributes
        self.tam_solution = len(self.durations)  # one random key per job
        self.LS_type = "Best"
        self.dict_best = {}
        self.instance_name = "sequencing"

        # Search parameters (RKO picks among the listed values)
        self.BRKGA_parameters = {"p": [200], "pe": [0.2], "pm": [0.05], "rhoe": [0.7]}
        self.SA_parameters = {"SAmax": [100], "alphaSA": [0.9], "betaMin": [0.01],
                              "betaMax": [0.05], "T0": [1000]}
        self.ILS_parameters = {"betaMin": [0.1], "betaMax": [0.2]}
        self.VNS_parameters = {"kMax": [5], "betaMin": [0.05]}
        self.LNS_parameters = {"betaMin": [0.1], "betaMax": [0.3], "TO": [100],
                               "alphaLNS": [0.9]}
        self.PSO_parameters = {"PSize": [100], "c1": [2.05], "c2": [2.05], "w": [0.73]}
        self.GA_parameters = {"sizePop": [100], "probCros": [0.98], "probMut": [0.005]}

    def decoder(self, keys):
        return np.argsort(keys)  # job order: smallest key first

    def cost(self, solution, final_solution=False):
        finish = np.cumsum(self.durations[solution])
        late = np.maximum(finish - self.due_dates[solution], 0.0)
        return float(late.sum())  # RKO minimizes this


if __name__ == "__main__":
    rng = np.random.default_rng(0)
    env = SequencingEnv(rng.integers(1, 20, 80), rng.integers(50, 600, 80))

    solver = RKO(env, logger="none")
    cost, keys, seconds_to_best = solver.solve(time_total=20, brkga=1, sa=1)

    order = env.decoder(keys)  # solve() returns the keys, not the solution
    os.makedirs("output", exist_ok=True)
    with open("output/output.json", "w") as f:
        json.dump(
            {
                "objective": cost,
                "rows": [{"name": f"Job {int(j)}", "value": int(env.durations[j])}
                         for j in order[:10]],
            },
            f,
        )
    print(f"total tardiness {cost:.1f}, best found after {seconds_to_best:.1f}s")

Match the workers to the kernel

In solve(), each of brkga, ms, sa, vns, ils, lns, pso and ga is the number of worker processes for that method. Keep the sum at or below the kernel's CPUs. More workers than CPUs only makes them slow each other down.

Don't size the mix from os.cpu_count(). In a container with a CPU limit it can report the host's cores instead of your kernel's.

A few other settings matter:

Let Harumi AI Chat do it

Harumi AI Chat knows that RKO is available and, in a project, will consider it for large combinatorial problems that an exact model can't solve in time. For better results, install the RKO modeling skill into the project:

1. Open Memories & Skills in the project sidebar and switch to the Library tab.
2. Find RKO modeling (search for "RKO", or filter by the Problem type category).
3. Click Install.

Installing copies the skill into the project's repository as skills/rko-modeling/SKILL.md, where you can edit it like any other skill. See Memories & Skills for how skills work.

Read the result as a heuristic

Whatever the cost, RKO has no proof that a better solution doesn't exist. Before you rely on a result:

• decode the final keys and check the solution independently (every item placed once, capacities and deadlines respected), because a missing penalty in the cost can make an infeasible solution look cheap;
• compare it with a simple baseline, such as a greedy rule or the exact solution of a small instance;
• run it twice. RKO has no seed setting, so each run is a fresh random search, and a large difference between runs means the time budget is too short.