Skip to content

BitType Skills in JOpt.TourOptimizer

Multiple order-of-magnitude runtime speedups compared to TypeConstraint

BitType is a high-performance representation of dictionary-backed bitsets for ultra-fast eligibility checks in routing and dispatch optimization. In many real-world problems, eligibility constraints determine which resource may serve which node, and these checks are executed millions of times inside the move loop. BitType targets this runtime hotspot directly. It delivers orders-of-magnitude faster eligibility evaluation while preserving the exact same feasibility semantics and optimization behavior. The model meaning does not change, only the internal representation becomes significantly more efficient.

Overview

Executive summary

In large instances, eligibility constraints become a dominant runtime factor. This is typically not because routing is inherently difficult, but because eligibility is checked millions of times during construction and improvement phases.

BitType is JOpt’s high-performance representation for “type/skill” matching. Instead of comparing strings or scanning collections, it:

  1. normalizes skill strings into dictionary IDs (integers),
  2. stores skill sets as compact bitsets (one bit per skill),
  3. evaluates matching using CPU-efficient bit operations.

In practice, this yields multiple order-of-magnitude speedups for skill-heavy instances. These speedups do not require relaxing constraints or changing the objective. BitType keeps the same eligibility semantics and supports the same modeling features: plain “type” constraints, type + expertise constraints, and both hard and soft behavior via cost models.

The problem BitType solves

1) Eligibility checks are extremely frequent

During optimization, the engine repeatedly considers moves like inserting a node into a route, swapping nodes between routes, reassigning a node to another resource, or rebuilding parts of the solution. Each candidate move triggers eligibility evaluation.

Eligibility checks usually answer three questions:

  • Does this resource have the required skills?
  • Does it meet the minimum or maximum expertise level?
  • If it does not match perfectly, how should the optimizer penalize the mismatch (soft constraint)?

When instances are large and constraints are rich, these checks become a main runtime driver. Making eligibility cheaper immediately accelerates the whole search.

2) Naive matching is expensive

Common implementations represent skills using lists of strings, sets of keys, or nested maps. Even with hashing, matching can degrade into repeated allocations, repeated hashing, and repeated iteration across required skills.

BitType replaces this with constant-time bitwise operations on compact data.

Core idea: dictionary → integer → bitset

BitType is based on a simple pipeline.

1) Skill names as strings
You keep human-readable skills such as "REPAIR", "WEIGHT", "ELECTRICAL", "ADR", "FORKLIFT".

2) Dictionary assignment
Each unique skill string is added to a shared dictionary and mapped to an integer ID.

3) Bit assignment
That integer ID corresponds to a bit position inside a bitset.

4) Matching
Eligibility becomes a set-inclusion test implemented as a bitwise AND check:

(requiredBits AND offeredBits) == requiredBits

If the condition is true, the resource provides all required skills. This is the same reasoning as “set inclusion”, but executed using bit operations rather than per-skill iteration.

Example of AND Operation

Required skills (defined by a node) are represented by requiredBits. Offered skills (defined by a resource) are represented by offeredBits. Each bit corresponds to one skill in the shared dictionary.

The AND operation clears any bit that is not present in both sets. If a required bit disappears, eligibility fails.

Passing Case

The Required Bits are identical to the AND Result → Passing.

Required Bits:  1 0 1 1 0 0 1
Offered Bits:   1 1 1 1 0 0 1
--------------------------------
AND Result:     1 0 1 1 0 0 1
--------------------------------
Diff:           0 0 0 0 0 0 0

All required bits are preserved after the AND operation. The Diff only contains zeros, so no required skill is missing.

Failing Case (Missing Skills)

The Required Bits are not equal to the AND Result → Failing.

Required Bits:  1 1 1 1 0 0 1
Offered Bits:   0 0 1 1 0 0 1
--------------------------------
AND Result:     0 0 1 1 0 0 1
--------------------------------
Diff:           1 1 0 0 0 0 0

The Diff highlights missing required skills. In this example, skills at bit positions 0 and 1 are required but not offered.

Why it is faster (in plain terms)

Bitsets are fast because they are compact and cache-friendly. Many skills fit into a handful of machine words, and matching can be evaluated with word-level operations that modern CPUs execute extremely efficiently.

This shifts matching from “loop through skills and hash strings” to “a few CPU instructions”. Because the meaning of eligibility does not change, optimization quality does not get worse. You simply spend much less time on the same checks.

Implementation guide (step-by-step)

Step 1 — Define skills consistently

Keep a canonical definition of skill names as strings, typically as constants such as SKILL_TYPE_REPAIR, SKILL_TYPE_WEIGHT, and SKILL_TYPE_ELECTRICAL. Consistent naming matters because the dictionary maps unique strings. Stable keys also help when skills are part of an external data contract (files, REST APIs, or databases).

Step 2 — Add BitType requirements to nodes

Attach a BitType-with-expertise constraint/condition to the node and populate it. The method addDictType(...) expresses a very specific intent: add this skill name to the shared dictionary (if it is not already present), then set the corresponding bit in the requirement set. This keeps string skills convenient for domain models while enabling bitset matching in the optimizer.

Add BitTypeWithExpertiseConstraint to a Node

In many cases you combine skill requirements with expertise thresholds (minimum/maximum) and a cost model. A common pattern is to make “nice-to-have” skills soft and “must-have” skills hard.

private static final String SKILL_TYPE_REPAIR = "Roof_Repair_Clean";
private static final String SKILL_TYPE_WEIGHT = "Weight_Including_Equimpment";

// Create the constraint
BitTypeWithExpertiseConstraint repairConstraint = new BitTypeWithExpertiseConstraint();

// Set a cost model - See cost models
repairConstraint.setSkillCostingModel(SkillInfoCostModel.PENALIZE_MATCHING_SKILL_HIGH_DELTA);

// Define min requirement
int minExpertiseLevel = 2;
boolean isMinExpertiseLevel = true;

TypeLevelRequirement minReq = TypeLevelRequirement.of(minExpertiseLevel, isMinExpertiseLevel);
repairConstraint.addDictType(SKILL_TYPE_REPAIR, minReq);

// We want a match of the SKILL_TYPE_REPAIR but only if possible
repairConstraint.setIsHard(false);

You can add additional skill requirements, for example a legal requirement that must always be satisfied:

BitTypeWithExpertiseConstraint weightConstraint = new BitTypeWithExpertiseConstraint();
weightConstraint.setSkillCostingModel(SkillInfoCostModel.NO_PENALIZE_MATCHING_SKILL);

int maxWeightLevel = 10;
boolean weightIsMinLevel = false;

TypeLevelRequirement maxReq = TypeLevelRequirement.of(maxWeightLevel, weightIsMinLevel);
weightConstraint.addDictType(SKILL_TYPE_WEIGHT, maxReq);

// We want a match of the SKILL_TYPE_WEIGHT in any case as it is a legal requirement
weightConstraint.setIsHard(true);

Finally, attach the constraints to the node:

node.addConstraint(repairConstraint);
node.addConstraint(weightConstraint);

Step 3 — Add BitType qualifications to resources

Next, provide the skills (and optionally skill levels) as a BitType qualification on the resource. A resource becomes eligible whenever a node’s required bits are a subset of the resource’s offered bits. If a node does not require a specific expertise threshold, any resource with the skill is eligible.

Add BitTypeWithExpertiseQualification to a Resource

// Setting Qualifications with Expertise

int jackExpertiseLevel = 10;
int jackWeightLevel = 5;

int paulaExpertiseLevel = 5;
int paulaWeightLevel = 2;

BitTypeWithExpertiseQualification jackQualification = new BitTypeWithExpertiseQualification();
jackQualification.addDictType(SKILL_TYPE_REPAIR, TypeLevelOffering.of(jackExpertiseLevel));
jackQualification.addDictType(SKILL_TYPE_WEIGHT, TypeLevelOffering.of(jackWeightLevel));

BitTypeWithExpertiseQualification paulaQualification = new BitTypeWithExpertiseQualification();
paulaQualification.addDictType(SKILL_TYPE_REPAIR, TypeLevelOffering.of(paulaExpertiseLevel));
paulaQualification.addDictType(SKILL_TYPE_WEIGHT, TypeLevelOffering.of(paulaWeightLevel));

// Adding the Qualifications to the Resources
resourceJack.addQualification(jackQualification);
resourcePaula.addQualification(paulaQualification);

Step 4 — Decide hard vs soft behavior (and select a cost model)

Use hard constraints when matching must always hold (feasibility-by-construction). Use soft constraints when violations are allowed but should be discouraged. Cost models apply structured penalties and help the optimizer distinguish between “acceptable” and “ideal” assignments without turning the instance infeasible.

Step 5 — Validate using a small demo, then scale

Start with a small set of nodes and resources to validate eligibility and penalties. Once verified, scale up to real instance sizes and observe the runtime improvements. This is where BitType typically pays off: large instances with many skills and many eligibility checks.

Capability: “Type”, “Type + Expertise”, and cost models

1) Plain type matching (hard)

Use this when a node must only be served by resources that provide a skill. Typical scenarios include technician certification, vehicle equipment, legal compliance (ADR, temperature control), and service territory entitlements.

In JOpt, hard skill eligibility is a hard constraint. It is typically fulfilled structurally (feasible-by-construction), not by inflating costs.

2) Type + expertise level (hard or soft)

Sometimes it is not enough that a resource has the skill — it must meet a threshold. This can be a minimum level (for example, “at least senior”) or a maximum level (for example, “do not assign a highly specialized resource to basic tasks”).

BitType supports expertise levels without losing performance. The optimizer first performs the fast bitset check for skill presence. Only if that passes does it check expertise levels for those skills.

3) Soft preferences via cost models

Often you want a preferred match (for example, higher skill level is better), but still allow fallback if needed. Cost models support this by keeping the move feasible while adding a structured penalty for mismatches.

This is especially useful in real data, where inputs can be imperfect or the instance can be overconstrained.

Cost Models (Detailed Explanation)

The cost model augments the fast BitType eligibility check with a quantitative evaluation of how well a resource matches the requested expertise level. The bitset check establishes structural feasibility — whether the skill exists. The cost model then guides the optimizer by assigning penalties based on the difference (delta) between required and offered expertise.

This separation is deliberate. It keeps the hot path fast, while still allowing nuanced business behavior for ranking and selection.

1. NO_PENALIZE_MATCHING_SKILL

This model introduces no penalty as long as the required expertise condition is satisfied. If a node requires at least level 5 and the resource offers level 8, the assignment is fully acceptable and does not increase cost.

Use this when the business rule is “meet or exceed the requirement,” and higher expertise is not considered wasteful. This is common for legal, safety, or compliance-driven constraints.

Behavior summary: below minimum is infeasible if the constraint is hard; meeting or exceeding the requirement adds zero penalty.

2. PENALIZE_MATCHING_SKILL_LOW_DELTA

This model prefers assigning the highest qualified resource possible among feasible candidates. If a minimum expertise level is required, the assignment must not go below that threshold. Among candidates that meet the threshold, higher expertise is preferred.

The penalty is calculated relative to the global maximum expertise level rather than the required level:

cost ∝ (GLOBAL_MAX_LEVEL − ACTUAL_LEVEL)

This means the closer the resource’s expertise is to the global maximum, the lower the penalty. Use this when you want to prioritize top-qualified specialists, for example to maximize quality or customer satisfaction.

3. PENALIZE_MATCHING_SKILL_HIGH_DELTA

This model enforces a stronger preference for precise matching by penalizing deviations from the requested expertise more sharply. The optimizer is encouraged to find the closest possible match.

Use this when precision matters, such as contract-based service levels, cost-sensitive service tiers, or when you want to avoid “overskilling” and preserve balanced utilization.

Hard vs. Soft Interaction

The cost model interacts with the isHard setting:

  • With hard constraints (isHard = true), the requirement must be satisfied. The cost model influences preference among valid candidates.
  • With soft constraints (isHard = false), the optimizer may accept imperfect matches, but penalties influence ranking and solution quality.

Conceptual Summary

The BitType check answers: Is this assignment structurally valid?
The cost model answers: How good is this assignment compared to other feasible options?

Together, they separate feasibility from optimization quality: eligibility remains ultra-fast, and preferences remain expressive.

When to use BitType (practical guidance)

Use BitType if you have many resources and nodes, many skills, frequent eligibility checks, or expertise levels. It is also a strong fit if profiling shows skill constraints dominating runtime.

BitType is ideal when you need type logic throughout the pipeline: construction, neighborhood moves, and post-processing/explainability.

Design notes for enterprise projects

Stable dictionary IDs

For stable, reproducible behavior across systems, keep skill naming stable and avoid dynamically inventing new skill strings at runtime.

Multi-client / REST usage

If you integrate via REST/OpenAPI, treat skill definitions as part of your data contract. Use stable skill keys and version skill catalogs if your domain evolves.

References

Example code

Appendix: mental model cheat sheet

  • Skill catalog (strings) → dictionary IDs → bitset
  • Eligibility = required ⊆ offered using bit operations
  • Expertise levels are checked only after the fast bitset pass
  • Hard skill constraints are fulfilled by architecture, not by “high cost”