Optimization Algorithms

• 1: Construction Heuristics
• 2: Local Search
• 3: Exhaustive Search
• 4: Move Selectors

1. Construction Heuristic
   └── Builds initial solution (fast, may be suboptimal)

2. Local Search
   └── Iteratively improves solution (most time spent here)

3. (Optional) Exhaustive Search
   └── Proves optimality (only feasible for small problems)

1 - Construction Heuristics

A construction heuristic builds an initial solution by assigning values to all planning variables. It runs fast but may not find an optimal solution—that’s the job of local search.

Why Construction Heuristics?

• Fast initialization: Quickly assigns all variables
• Warm start: Gives local search a good starting point
• Automatic termination: Stops when all variables are assigned

First Fit

Algorithm

First Fit cycles through planning entities in default order, assigning each to the best available value:

1. Take the first unassigned entity
2. Try each possible value
3. Assign the value with the best score
4. Repeat until all entities are assigned

Behavior

Entity 1 → Best value found → Assigned (never changed)
Entity 2 → Best value found → Assigned (never changed)
Entity 3 → Best value found → Assigned (never changed)
...

Limitations

• Order matters: Early assignments may block better solutions
• No backtracking: Once assigned, values don’t change
• May not find feasible solution if early choices are poor

First Fit Decreasing

Algorithm

Like First Fit, but sorts entities by difficulty first:

1. Sort entities by difficulty (hardest first)
2. Assign difficult entities first
3. Easy entities fit in remaining slots

Why It Helps

Difficult entities (those with fewer valid options) are assigned first while there are more options available. Easy entities can usually fit anywhere.

Example

For school timetabling:

• Teachers with many constraints → assigned first
• Teachers with few constraints → assigned last

Default Behavior

SolverForge uses First Fit Decreasing by default. This works well for most problems without configuration.

How It Works Internally

Phase: Construction Heuristic
├── Sort entities by difficulty
├── For each unassigned entity:
│   ├── Try each value from value range
│   ├── Calculate score impact
│   └── Assign best value
└── Done when all entities assigned

Construction vs Local Search

When Construction Fails

If construction can’t find a feasible solution:

1. Overconstrained problem: Not enough resources for all entities
2. Tight constraints: Early assignments block later ones
3. Poor entity ordering: Important entities assigned last

Solutions

• Use medium constraints for “assign as many as possible”
• Add nullable planning variables
• Let local search fix infeasibilities

Monitoring Construction

from solverforge_legacy.solver import BestSolutionChangedEvent

def on_progress(event: BestSolutionChangedEvent):
    if not event.is_new_best_solution_initialized:
        print("Construction phase...")
    else:
        print("Local search phase...")

solver.add_event_listener(on_progress)

Performance Tips

Entity Ordering

Entities are processed in declaration order by default. For better results:

• Define difficult entities first in your entity list
• Or implement difficulty comparison

Value Ordering

Values are tried in order. Better default values lead to faster construction.

Next Steps

• Local Search - Improve the initial solution
• Move Selectors - Customize optimization moves

2 - Local Search

Local search algorithms iteratively improve a solution by making small changes called “moves.” This is where the solver spends most of its time finding better solutions.

How It Works

Start with initial solution
Repeat until termination:
    1. Generate possible moves
    2. Evaluate each move's score impact
    3. Select a move based on acceptance criteria
    4. Apply the move
    5. Update best solution if improved

Local Search Algorithms

Late Acceptance

Default algorithm. Accepts moves that improve on the solution from N steps ago.

• Balances exploration and exploitation
• Escapes local optima by accepting slightly worse moves
• Simple and effective for most problems

Hill Climbing

Only accepts moves that improve the score:

• Fast convergence
• Gets stuck in local optima
• Best for easy problems or quick iterations

Tabu Search

Maintains a list of recently made moves and forbids reversing them:

• Avoids cycles and revisiting solutions
• Explores more of the search space
• Memory overhead for tabu list

Simulated Annealing

Accepts worse moves with probability that decreases over time:

• “Temperature” controls acceptance probability
• High temperature = more exploration
• Low temperature = more exploitation
• Inspired by metallurgy annealing process

Great Deluge

Accepts moves above a rising “water level” threshold:

• Threshold increases over time
• Forces gradual improvement
• Similar to simulated annealing

Move Selection

Local search evaluates moves generated by move selectors:

Move Examples:
├── Change Move: lesson.room = Room B → Room C
├── Swap Move: lesson1.room ↔ lesson2.room
├── 2-Opt Move: Reverse segment in route
└── Custom Move: Domain-specific change

See Move Selectors for details.

Understanding the Search

Score Improvement Curve

Score
  ^
  |     ****
  |    *    **
  |   *       ***
  |  *           ****
  | *                ********
  |*                         ***************
  +---------------------------------> Time
     Construction   Local Search

Rapid improvement early, then diminishing returns.

Local Optima

A local optimum is a solution where no single move improves the score, but better solutions exist:

Score
  ^
  |        *
  |       * *        Global optimum
  |      *   *      ↓
  |     *     *    *
  |    *       *  * *
  |   *    ↑    **   *
  |  *     Local      *
  |        optimum
  +------------------------→ Solution Space

Algorithms like Late Acceptance and Tabu Search help escape local optima.

Termination

Local search runs until termination:

TerminationConfig(
    spent_limit=Duration(minutes=5),      # Time limit
    best_score_limit="0hard/0soft",       # Score target
    unimproved_spent_limit=Duration(seconds=60),  # Plateau detection
)

Choosing Termination Time

More time generally means better scores, with diminishing returns.

Monitoring Progress

def on_progress(event: BestSolutionChangedEvent):
    print(f"Time: {event.time_spent}")
    print(f"Score: {event.new_best_score}")
    print(f"Initialized: {event.is_new_best_solution_initialized}")

solver.add_event_listener(on_progress)

Score Plateaus

When the score stops improving:

1. Stuck in local optimum: Algorithm can’t find better moves
2. Near optimal: Little room for improvement
3. Constraint conflict: Hard constraints blocking progress

Detecting Plateaus

TerminationConfig(
    unimproved_spent_limit=Duration(seconds=60)  # Stop if no improvement
)

Algorithm Selection

Start with the default (Late Acceptance) and only change if benchmarking shows improvement.

Performance Tips

1. Let It Run Longer

More time usually means better scores.

2. Optimize Constraints

Slow constraints = fewer moves evaluated per second.

3. Use Appropriate Moves

Some moves work better for certain problems (see Move Selectors).

4. Benchmark

Test different algorithms and parameters on your specific problem.

Next Steps

• Move Selectors - Customize move generation
• Benchmarking - Compare configurations

3 - Exhaustive Search

Exhaustive search algorithms explore all possible solutions to find the optimal one. They guarantee the best solution but are only practical for small problems.

When to Use

Exhaustive search is only feasible when:

• Problem is very small (< 20 entities, few values)
• You need a guaranteed optimal solution
• You have time to wait for completion

For most problems, local search finds near-optimal solutions much faster.

Branch and Bound

The main exhaustive search algorithm. It systematically explores the solution space while pruning branches that can’t improve on the best solution found.

How It Works

                    Root (no assignments)
                   /    |    \
            Entity1=A  Entity1=B  Entity1=C
              /  \        |          |
        E2=A  E2=B    E2=A         ...
        /  \    |      |
      E3=A ...  X    (pruned)
       |
    (Best?)

1. Build a tree of partial solutions
2. At each node, try assigning a value to the next entity
3. Calculate a score bound for the branch
4. If bound is worse than best known solution, prune the branch
5. Continue until all branches are explored or pruned

Pruning

Pruning is key to performance:

Best so far: -5hard/0soft

Current partial: -3hard/?soft
→ Continue (might improve)

Current partial: -10hard/?soft
→ Prune (can't beat best)

Brute Force

Tries every possible combination without pruning:

• Guarantees optimal solution
• Extremely slow (exponential time)
• Only for very small problems or validation

Complexity

For N entities with M possible values each:

• Combinations: M^N
• Example: 10 entities × 10 values = 10^10 = 10 billion combinations

Comparison

Practical Limits

When Local Search is Better

For most real problems, local search is the right choice:

Hybrid Approach

Use exhaustive search to validate local search:

def validate_optimality(problem):
    """
    For small problems, verify local search finds optimal.
    For testing only!
    """
    # Run local search
    local_solution = run_local_search(problem)

    # Run exhaustive search (small problems only!)
    optimal_solution = run_exhaustive(problem)

    assert local_solution.score == optimal_solution.score

Best Practices

Do

• Use exhaustive search only for very small problems
• Use it to validate your constraint model on tiny examples
• Understand that it’s for special cases, not general use

Don’t

• Expect exhaustive search to scale
• Use it in production for real-world problems
• Wait for results on large problems (it won’t finish)

Next Steps

• Local Search - For practical problem sizes
• Benchmarking - Compare approaches

4 - Move Selectors

Move selectors generate the moves that local search evaluates. Different move types are effective for different problems.

Move Types

Change Move

Changes one planning variable to a different value:

Before: lesson.room = Room A
After:  lesson.room = Room B

Best for: Assignment problems, scheduling

Swap Move

Swaps values between two entities:

Before: lesson1.room = Room A, lesson2.room = Room B
After:  lesson1.room = Room B, lesson2.room = Room A

Best for: When both changes are needed for improvement

Pillar Change Move

Changes multiple entities with the same value simultaneously:

Before: [lesson1, lesson2, lesson3].room = Room A
After:  [lesson1, lesson2, lesson3].room = Room B

Best for: Grouped entities that should move together

Pillar Swap Move

Swaps values between two groups of entities:

Before: [l1, l2].room = A, [l3, l4].room = B
After:  [l1, l2].room = B, [l3, l4].room = A

Best for: Problems with entity groups

List Change Move (for List Variables)

Changes an element’s position in a list:

Before: vehicle.visits = [A, B, C, D]
Move: Move C from position 2 to position 0
After:  vehicle.visits = [C, A, B, D]

Best for: Routing, sequencing

List Swap Move

Swaps two elements within or between lists:

Before: vehicle1.visits = [A, B], vehicle2.visits = [C, D]
Move: Swap B and C
After:  vehicle1.visits = [A, C], vehicle2.visits = [B, D]

Best for: Rebalancing routes

2-Opt Move

Reverses a segment of a list:

Before: vehicle.visits = [A, B, C, D, E]
Move: Reverse [B, C, D]
After:  vehicle.visits = [A, D, C, B, E]

Best for: Routing (reduces “crossing” paths)

Sublist Change Move

Moves a subsequence to a different position:

Before: vehicle.visits = [A, B, C, D, E]
Move: Move [B, C] to end
After:  vehicle.visits = [A, D, E, B, C]

Best for: Batch relocations

Sublist Swap Move

Swaps two subsequences:

Before: vehicle1.visits = [A, B, C], vehicle2.visits = [X, Y, Z]
Move: Swap [B, C] and [Y, Z]
After:  vehicle1.visits = [A, Y, Z], vehicle2.visits = [X, B, C]

Best for: Inter-route optimization

Default Move Selectors

SolverForge automatically selects appropriate moves based on your variable types:

Move Selection Process

1. Selector generates candidate moves
2. Each move is evaluated (score calculated)
3. Acceptance criteria decides to apply or not
4. Repeat

Move Efficiency

Incremental Scoring

Moves are scored incrementally—only recalculating affected constraints:

Change lesson.room = A → B
Only recalculate:
├── Room conflict (for A and B)
├── Teacher room stability
└── (Other constraints unaffected)

This makes move evaluation fast.

Move Speed

Typical moves evaluated per second:

More moves = more exploration = better solutions (usually).

Filtering Moves

The solver automatically filters invalid moves:

• Moves that don’t change anything (same value)
• Moves that violate pinning
• Moves on uninitialized variables

Move Caching

To avoid regenerating the same moves:

• Construction moves are cached
• Local search moves are regenerated (solution changes)

Performance Impact

Move selection affects:

1. Diversity: Different move types explore different parts of the search space
2. Speed: Some moves are faster to evaluate
3. Effectiveness: Some moves are more likely to find improvements

Problem-Specific Guidance

Scheduling (Timetabling, Shifts)

• Change moves: Reassign timeslot, room, employee
• Swap moves: Exchange assignments
• Default selection works well

Routing (VRP)

• List moves: Reorder visits
• 2-Opt: Eliminate crossing paths
• Sublist moves: Move segments between vehicles

Assignment (Task Assignment, Bin Packing)

• Change moves: Reassign to different resource
• Swap moves: Exchange assignments
• Pillar moves: Move groups together

Troubleshooting

Slow Moves

If moves are slow:

1. Check constraint complexity
2. Optimize filtering (use joiners)
3. Reduce problem size

Poor Improvement

If solutions don’t improve:

1. Run longer
2. Ensure moves can reach better solutions
3. Check if stuck in local optimum

Next Steps

• Local Search - How moves are used
• Performance - Speed up constraint evaluation