local_search

This notebook provides documentation for the function local_search, which performs a local search to optimize a scheduling solution. The function iteratively explores the neighborhood of the current best solution by switching a given number of patients. It utilizes precomputed convolution results and a set of adjustment vectors (v_star) to evaluate and improve the objective function.

Function Documentation

local_search(x: Union[List[int], np.ndarray], d: int, convolutions: Dict[int, np.ndarray], w: float, v_star: np.ndarray, size: int = 2, echo: bool = False) -> Tuple[np.ndarray, float]

Description

The local_search function optimizes a schedule by iteratively exploring its neighborhood. Starting with an initial solution x, the function computes its objective value using the precomputed convolutions of the service time probability mass function. The neighborhood is generated by combining adjustment vectors from v_star (using a powerset-based approach) and filtering out candidates that contain negative values. The search continues until no further improvement is found for neighborhoods up to the specified size. The objective function combines expected average waiting time per patient and spillover time weighted by w.

Parameters

  • x (Union[List[int], np.ndarray]):
    The initial solution vector representing the schedule. It can be provided as a list of integers or as a NumPy array.

  • d (int):
    The duration threshold for a time slot. It is used to adjust the service process and waiting time distribution.

  • convolutions (Dict[int, np.ndarray]):
    A dictionary containing precomputed convolutions of the service time PMF. The key 1 represents the adjusted service time distribution, and other keys represent the convolution for the corresponding number of scheduled patients.

  • w (float):
    The weighting factor for combining the two performance objectives: expected waiting time and expected spillover time.

  • v_star (np.ndarray):
    A 2D NumPy array of adjustment vectors. Each row in v_star is used to modify the current solution vector in order to generate its neighborhood.

  • size (int, optional):
    The maximum number of patients to switch (i.e., the size of the neighborhood to explore) during the local search. Defaults to 2.

  • echo (bool, optional):
    A flag that, when set to True, prints progress and debugging messages during the search process. Defaults to False.

Returns

  • Tuple[np.ndarray, float]:
    A tuple containing:
    • The best solution found as a 1D NumPy array.
    • The corresponding cost (objective value) as a float.

Example

import numpy as np
from functions import local_search, calculate_objective_serv_time_lookup, compute_convolutions, get_v_star, powerset

from typing import List, Dict, Tuple, Union

def ways_to_distribute(N: int, T: int) -> List[List[int]]:
    """
    Compute all possible ways to distribute N identical items into T bins.
    
    Each distribution is represented as a list of T nonnegative integers whose sum is N.
    
    Parameters:
        N (int): Total number of identical items.
        T (int): Number of bins.
        
    Returns:
        List[List[int]]: A list of distributions. Each distribution is a list of T integers that sum to N.
        
    Example:
        >>> ways_to_distribute(3, 2)
        [[0, 3], [1, 2], [2, 1], [3, 0]]
    """
    # Base case: only one bin left, all items must go into it.
    if T == 1:
        return [[N]]
    
    distributions = []
    # Iterate over possible numbers of items in the first bin
    for i in range(N + 1):
        # Recursively distribute the remaining items among the remaining bins.
        for distribution in ways_to_distribute(N - i, T - 1):
            distributions.append([i] + distribution)
            
    return distributions
  
def choose_best_solution(solutions: List[np.ndarray], d: int, convs: Dict[int, np.ndarray], w: float, v_star: np.ndarray) -> Tuple[np.ndarray, float]:
    """
    Choose the best solution from a list of solutions based on the objective function.
    
    Parameters:
        solutions (List[np.ndarray]): A list of solution vectors.
        d (int): Duration threshold for a time slot.
        convs (Dict[int, np.ndarray]): Precomputed convolutions of the service time PMF.
        w (float): Weighting factor for the objective function.
        
    Returns:
        Tuple[np.ndarray, float]: The best solution and its corresponding cost.
    """
    best_solution = None
    best_cost = float('inf')
    
    for solution in solutions:
        waiting_time, spillover = calculate_objective_serv_time_lookup(solution, d, convs)
        cost = w * waiting_time /N + (1 - w) * spillover
        if cost < best_cost:
            best_solution = solution
            best_cost = cost
            
    return np.array(best_solution), best_cost

# Example schedule: initial solution vector
x_initial = [3, 2, 1, 0]
T = len(x_initial)
N = sum(x_initial)

# Duration threshold for a time slot
d = 5

# Example probability mass function and no-show probability
service_time = np.zeros(11)
service_time[3] = 0.2
service_time[5] = 0.3
service_time[8] = 0.5
q = 0.1

# Compute convolutions (precomputed service time distributions)
convs = compute_convolutions(service_time, N=N, q=q)

# Weighting factor for the objective function
w = 0.5

# Generate adjustment vectors for the schedule (v_star)
v_star = get_v_star(len(x_initial))

# Perform local search to optimize the schedule
best_solution, best_cost = local_search(x_initial, d, convs, w, v_star, size=T, echo=True)

print("Best Solution:", best_solution)
print("Best Cost:", best_cost)
Initial solution: [3 2 1 0], cost: 37.71594467672401
Running local search with switching 1 patient(s)
Size of neighborhood: 3
Found better solution: [2 2 1 1], cost: 30.52386358592401
Running local search with switching 1 patient(s)
Size of neighborhood: 4
Found better solution: [1 2 1 2], cost: 25.53066071370001
Running local search with switching 1 patient(s)
Size of neighborhood: 4
Running local search with switching 2 patient(s)
Size of neighborhood: 6
Found better solution: [1 1 1 3], cost: 22.474543162500005
Running local search with switching 1 patient(s)
Size of neighborhood: 4
Running local search with switching 2 patient(s)
Size of neighborhood: 6
Running local search with switching 3 patient(s)
Size of neighborhood: 4
Best Solution: [1 1 1 3]
Best Cost: 22.474543162500005
import unittest
import numpy as np
from functions import local_search, compute_convolutions, get_v_star

class TestLocalSearch(unittest.TestCase):
    def test_local_search_improvement(self):
        # Set up a simple test with a known schedule and parameters
        x_initial = [3, 2, 1, 0]
        T = len(x_initial)
        N = sum(x_initial)
        d = 5
        service_time = np.zeros(11)
        service_time[3] = 0.2
        service_time[5] = 0.3
        service_time[8] = 0.5
        q = 0.1
        convs = compute_convolutions(service_time, N=N, q=q)
        w = 0.5
        v_star = get_v_star(len(x_initial))
        
        # Perform local search
        best_solution, best_cost = local_search(x_initial, d, convs, w, v_star, size=T, echo=False)
        print("Best Solution:", best_solution, "Best Cost:", best_cost)
        
        # Iterate over all solutions and choose best solution
        solutions = ways_to_distribute(N, T)
        best_solution_brute, best_cost_brute = choose_best_solution(solutions, d, convs, w, v_star)
        print("Best Brute-force Solution:", best_solution_brute, "Best Brute-force Cost:", best_cost_brute)
        
        # Verify that the local search solution is equal to the brute-force solution
        self.assertTrue(np.array_equal(best_solution, best_solution_brute), "The local search solution should match the brute-force solution.")
        
        # Verify that the returned solution has the same length as the initial schedule
        self.assertEqual(len(best_solution), len(x_initial), "The optimized solution should have the same length as the initial solution.")
        
        # Check that the cost is a float and that a solution is returned
        self.assertIsInstance(best_cost, float, "Cost should be a float value.")

if __name__ == '__main__':
    unittest.main(argv=[''], exit=False)
F
======================================================================
FAIL: test_local_search_improvement (__main__.TestLocalSearch.test_local_search_improvement)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/var/folders/gf/gtt1mww524x0q33rqlwsmjw80000gn/T/ipykernel_37119/3482521855.py", line 31, in test_local_search_improvement
    self.assertTrue(np.array_equal(best_solution, best_solution_brute), "The local search solution should match the brute-force solution.")
AssertionError: False is not true : The local search solution should match the brute-force solution.

----------------------------------------------------------------------
Ran 1 test in 0.010s

FAILED (failures=1)
Initial solution: [3 2 1 0], cost: 37.71594467672401
Best Solution: [1 1 1 3] Best Cost: 22.474543162500005
Best Brute-force Solution: [2 1 1 2] Best Brute-force Cost: 9.894705450000002