How to apply an enumeration algorithm into a problem?

Question

I am new to stackoverflow and I wonder if there is a suitable method/algorithm to solve my example problems in order to generate a desired solution that respect some conditions of the problems. Here is my json file(example1.json) as you can find from here: https://gitlab.com/Schrodinger168/practice/-/blob/master/example1.json

I will explain the csv file and what I want to generate as below:

For Ressources there are for example Ressources_X that X here can be a value from 1 to 9. All Ressource_X have their min and max values that needed to be respect as the final solution(will say below) cannot smaller than min and bigger than max for each day of all the Ressources_X.

For Seasons there are winter, summer, is... and each number correspond in those seasons refer to the day for example winter defines from day 1 to day 13 and the other seasons mean the same.

For Interventions: are tasks have to be planned. There are Intervention_X with corresponding workload containing Ressources_X that they have to use. Delta is the duration of the Intervention_X for example we can see in Intervention_625 as the first value(day 1) in the Delta list is 1.0 it means that if the Intervention_625 starts at day 1 it needs to finish in the same day(day 1) because its Delta value for day 1 is 1.0 and so on... Each Intervention_X has their own tmax for example Intervention_625 has tmax equal to 17 it means that it can be start between day 1 and day 17 as we wish to generate and the other tmax of other Intervention_X means the same.

For Exclusion there are some exceptions for example:

"E141["Intervention_315","Intervention_456","summer"] It means that Intervention_315 and Intervention_456 cannot start at the same day during the summer days(start at different days during the summer is ok) and the others mean the same.

T is the total duration here T = 17 it means that the duration of the overall work is 17 days

The solution I want to generate is the name of interventions and the starting day (tx,ty..) of each of those interventions for example:

Intervention_X tx

Intervention_Y ty

and so on... until all the Interventions have been used as they will use for only one time.

And the solution will make sure that it respects the conditions of using the Ressources (min, max) for each day, Exclusion, and the finish date can be T + 1 for maximum.

Here is my code to access to each nodes and values of my json file if needed:

class access_json:

    def __init__(self):
        self._resources = dict()
        self._seasons = dict()
        self._interventions = dict()
        self._exclusions = dict()
        
        self._NRESOURCES = 0
        self._NINTERVENTIONS = 0
        self._list_resources = list()
        self._list_interventions = list()
        
        self._T = 0
        
    def loadjson(self, fpath: str):
        js = dict()
        with open(fpath, 'r') as f:
            js = json.load(f)
        
        self._resources = js["Resources"]
        self._NRESOURCES = len(self._resources)
        self._list_resources = list(self._resources.keys())
        self._seasons = js["Seasons"]
        self._interventions = js["Interventions"]
        self._NINTERVENTIONS = len(self._interventions)
        self._list_interventions = list(self._interventions.keys())
        self._exclusions = js["Exclusions"]
        
        self._T = js["T"]

To solve the problems I try to use the permutation to exchange and replace those interventions in each day but it seems so long to do like that and did not generate the solution. Any help with codes, recommendation for how to apply the algorithm to solve this problem would be much appreciated. Thank you before hand!

Answer 1

This can be solved quickly using backtracking algorithm. In particular, with the stated data it can be solved in milliseconds.

Code

def overlap(x, y):
    '''
        Checks if two time segments overlap
    '''
    a, b = x
    c, d = y
    return a <= d and b >= c

def allocate(data, ans = None):
    '''
         Intervention schedule allocation based upon backtracking
    '''
    if ans is None:
        ans = {}
    
    if len(ans) == len(data["Interventions"]):
        # handled all the interventions
        yield ans
        
    # Check next intervention
    for intervention_name, intervention in data["Interventions"].items():
        if intervention_name not in ans:
            # will add items not in ans
            # last day intervention can be run
            last_day = min(data["T"], int(intervention["tmax"]))  
            
            for day in range(1, last_day+1):
                str_day = str(day)
                
                # different days intervention could be run
                delta = intervention["Delta"][day-1]  # number of days it takes to run
                
                if day + delta <= last_day + 1: 
                    # must finish within last day
                    # Check that there are sufficient resources
                    resource_usage = {}
                
                        
                    missing_resources = False
                    for resource_name, v in intervention["workload"].items():
                        if not str_day in v:
                            missing_resources = True
                            break
                            #raise Exception(f'{intervention_name} resources {k} missing day {str_day}')
                        usage_key = (resource_name, day)  # pair: (resource name, day) as key
                        resource_usage[usage_key] = v[str_day][str_day]
                    if missing_resources:
                        continue # one resource has no resources for a day
                    
                    # Resources needed by items in list for this day
                    for ans_name, ans_response in ans.items():
                        ans_day = ans_response["Day"]
                        ans_delta = ans_response["Delta"]
                        
                        if overlap([day, day+delta-1], [ans_day, ans_day+ans_delta-1]):
                            # An intervention in answer overlaps with current intervention
                            for resource_name, v_resource in ans_response["Resources"].items():
                                for overlap_day in range(day, day+int(delta)):
                                    # Get resource usage for each day of overlap
                                    usage_key = (resource_name, overlap_day)
                                    if not usage_key in resource_usage:
                                        resource_usage[usage_key] = 0
                                    resource_usage[usage_key] += v_resource
                    
                    # Check resource less than max
                    resources = data["Resources"]
                    for usage_key, value in resource_usage.items():
                        resource_name, overlap_day = usage_key  # values from tuple
                        if value > resources[resource_name]["max"][day-1]: # max value for resoure for this day
                            break
                    else:
                        # Resource didn't exceed max
                        # Check on Exclusion
                        winter = data["Seasons"]['winter']
                        summer = data["Seasons"]['summer']
                        isa = data["Seasons"]['is']
                        if str_day in winter:
                            season = "winter"
                        elif str_day in summer:
                            season = "summer"
                        elif str_day in isa:
                            season = "is"
                        else:
                            season = ""
                            
                        exclusions = data["Exclusions"]
                        bExclude = False
                        for k, v_lst in exclusions.items():
                            if season in v_lst and intervention_name in v_lst:
                                for intervention_k, ans_response in ans.items():
                                    if intervention_k in v_lst:
                                        ans_day = ans_response["Day"]
                                        ans_delta = ans_response["Delta"]
                                        if overlap([day, day+delta-1], [ans_day, ans_day+ans_delta-1]):
                                            bExclude = True
                                            break
                                if bExclude:
                                    break
                        if not bExclude:
                            # Resources used
                            response = {"Day": day, "Delta": intervention["Delta"][day-1]}
                            resources = {k:v[str_day][str_day] for k, v in intervention["workload"].items()}
                            response['Resources'] = resources
                            ans[intervention_name] = response
                            
                            yield from allocate(data, ans)
                            
                            # Remove last entry so we can try next iteration
                            del ans[intervention_name]   

                           

Usage

Using posted data set

# Loading data from local file
with open('resource_allocation/example1.json', 'r') as f:
    data = json.load(f)                          
       
# Get first solution using from allocate generator                 
answer = next(allocate(data), None)   
if answer:
    for name, intervention in answer.items():
        print(f'Intervention {name}')
        print(f'\tStart {intervention["Day"]}, Duration: {intervention["Delta"]}')
        resources = intervention["Resources"]
        for k, v in resources.items():
            print(f'\tResource: {k} Usage: {v}')
        print()

Output

Intervention Intervention_625
    Start 1, Duration: 1.0
    Resource: Ressources_2 Usage: 0.14
    Resource: Ressources_4 Usage: 0.14
    Resource: Ressources_7 Usage: 0.14
    Resource: Ressources_8 Usage: 0.056
    Resource: Ressources_9 Usage: 0.014

Intervention Intervention_31
    Start 1, Duration: 2.0
    Resource: Ressources_3 Usage: 0.86
    Resource: Ressources_4 Usage: 0.86
    Resource: Ressources_9 Usage: 0.086

Intervention Intervention_40
    Start 1, Duration: 1.0
    Resource: Ressources_2 Usage: 0.29
    Resource: Ressources_7 Usage: 0.29
    Resource: Ressources_9 Usage: 0.029

Intervention Intervention_224
    Start 1, Duration: 1.0
    Resource: Ressources_1 Usage: 0.71
    Resource: Ressources_9 Usage: 0.071

Intervention Intervention_702
    Start 1, Duration: 1.0
    Resource: Ressources_2 Usage: 0.43
    Resource: Ressources_9 Usage: 0.043

Intervention Intervention_19
    Start 1, Duration: 2.0
    Resource: Ressources_4 Usage: 0.86
    Resource: Ressources_8 Usage: 0.344
    Resource: Ressources_9 Usage: 0.086

Intervention Intervention_672
    Start 1, Duration: 1.0
    Resource: Ressources_3 Usage: 0.43
    Resource: Ressources_9 Usage: 0.043

Intervention Intervention_579
    Start 1, Duration: 1.0
    Resource: Ressources_8 Usage: 0.028
    Resource: Ressources_9 Usage: 0.014

Intervention Intervention_627
    Start 1, Duration: 2.0
    Resource: Ressources_2 Usage: 0.86
    Resource: Ressources_7 Usage: 0.86
    Resource: Ressources_8 Usage: 0.344
    Resource: Ressources_9 Usage: 0.086

Intervention Intervention_456
    Start 1, Duration: 1.0
    Resource: Ressources_4 Usage: 0.14
    Resource: Ressources_9 Usage: 0.014

Intervention Intervention_90
    Start 1, Duration: 1.0
    Resource: Ressources_2 Usage: 0.14
    Resource: Ressources_9 Usage: 0.014

Intervention Intervention_315
    Start 2, Duration: 1.0
    Resource: Ressources_4 Usage: 0.14
    Resource: Ressources_6 Usage: 0.14
    Resource: Ressources_7 Usage: 0.14
    Resource: Ressources_9 Usage: 0.014

Intervention Intervention_356
    Start 1, Duration: 1.0
    Resource: Ressources_7 Usage: 0.57
    Resource: Ressources_9 Usage: 0.057

Intervention Intervention_535
    Start 1, Duration: 1.0
    Resource: Ressources_3 Usage: 0.29
    Resource: Ressources_7 Usage: 0.29
    Resource: Ressources_9 Usage: 0.029

Intervention Intervention_595
    Start 1, Duration: 1.0
    Resource: Ressources_2 Usage: 0.14
    Resource: Ressources_9 Usage: 0.014

Intervention Intervention_592
    Start 1, Duration: 1.0
    Resource: Ressources_2 Usage: 0.14
    Resource: Ressources_8 Usage: 0.056
    Resource: Ressources_9 Usage: 0.014

Intervention Intervention_536
    Start 1, Duration: 1.0
    Resource: Ressources_3 Usage: 0.14
    Resource: Ressources_7 Usage: 0.14
    Resource: Ressources_9 Usage: 0.014

Intervention Intervention_150
    Start 1, Duration: 1.0
    Resource: Ressources_2 Usage: 0.14
    Resource: Ressources_6 Usage: 0.14
    Resource: Ressources_9 Usage: 0.014

Explanation

Pseudo Code

def allocate(data, ans = None):
    # initize answer if not initialized
    if ans is None:
        ans = {} # dictionary of interventions with name, day and resources used
        
    # Base case (check if solution found)
    if len(ans) == len(data["Interventions"]):
        yield ans  # let me know if you're not familiar with generators
        
    # Try remaining interventions (i.e. ones not in answer ans)
    #   Loop over all interventions
    for intervention_name, intervention in data["Interventions"].items():
        if intervention_name not in ans:
            # This intervention not in answer ans
            # Found out what day to run the intervention
            # last day to run
            last_day = min(data["T"], int(intervention["tmax"]))  
            
            for day in range(1, last_day+1):
                # Range of days to try running the intervention
                # make sure intervention finishes before last day
                delta = intervention["Delta"][day-1]  # number of days it takes to run
                if day + delta <= last_day + 1: 
                    # Check if intervention satisfies constraints if we add it on this day
                    
                    # 1--check sufficient resources
                    # logic for checking if suffient resources
                    # set sufficient_resources to True if sufficient, False otherwise
                    if sufficient_resources:
                        # 2--check if intervention compatible with others in list
                        #     i.e. can run on same day as others in ans
                        # set compatible to True if not excluded by others in list, False otherwise
                        if compatible:
                            # add intervention to ans for this day with the resources it uses on this day
                            # we call this response
                            
                            # Add intervention for this day
                            ans[intervention_name] = response
                            
                            # now recursive try other interventions
                            # This recursives tries other interventions
                            # by now successively trying the next intervention which is not in ans on a compatibl day
                            yield from allocate(data, and)

                            del ans[intervention_name] # remove last entry
        

Pseudo Code--non-generator function (but only find first solution)

def allocate(data, ans = None):
    # initize answer if not initialized
    if ans is None:
        ans = {} # dictionary of interventions with name, day and resources used
        
    # Base case (check if solution found)
    if len(ans) == len(data["Interventions"]):
        return True  # let me know if you're not familiar with generators
        
    # Try remaining interventions (i.e. ones not in answer ans)
    #   Loop over all interventions
    for intervention_name, intervention in data["Interventions"].items():
        if intervention_name not in ans:
            # This intervention not in answer ans
            # Found out what day to run the intervention
            # last day to run
            last_day = min(data["T"], int(intervention["tmax"]))  
            
            for day in range(1, last_day+1):
                # Range of days to try running the intervention
                # make sure intervention finishes before last day
                delta = intervention["Delta"][day-1]  # number of days it takes to run
                if day + delta <= last_day + 1: 
                    # Check if intervention satisfies constraints if we add it on this day
                    
                    # 1--check sufficient resources
                    # logic for checking if suffient resources
                    # set sufficient_resources to True if sufficient, False otherwise
                    if sufficient_resources:
                        # 2--check if intervention compatible with others in list
                        #     i.e. can run on same day as others in ans
                        # set compatible to True if not excluded by others in list, False otherwise
                        if compatible:
                            # add intervention to ans for this day with the resources it uses on this day
                            # we call this response
                            
                            # Add intervention for this day
                            ans[intervention_name] = response
                            
                            # now recursive try other interventions
                            # This recursives tries other interventions
                            # by now successively trying the next intervention which is not in ans on a compatibl day
                            if allocate(data, ans):
                                # Path forward found a solution
                                return True
                            else:
                                # Backtrack--this day won't work
                                # remove intervention since won't work for this day
                                del ans[intervention_name]   

Non-Generator Version

def overlap(x, y):
    '''
        Checks if two time segments overlap
    '''
    a, b = x
    c, d = y
    return a <= d and b >= c

def allocate2(data, ans = None):
    '''
         Intervention schedule allocation based upon backtracking
    '''
    if ans is None:
        ans = {}
    
    if len(ans) == len(data["Interventions"]):
        # handled all the interventions
        return ans
        
    # Check next intervention
    for intervention_name, intervention in data["Interventions"].items():
        if intervention_name not in ans:
            # will add items not in ans
            # last day intervention can be run
            last_day = min(data["T"], int(intervention["tmax"]))  
            
            for day in range(1, last_day+1):
                str_day = str(day)
                
                # different days intervention could be run
                delta = intervention["Delta"][day-1]  # number of days it takes to run
                
                if day + delta <= last_day + 1: 
                    # must finish within last day
                    # Check that there are sufficient resources
                    resource_usage = {}
                
                        
                    missing_resources = False
                    for resource_name, v in intervention["workload"].items():
                        if not str_day in v:
                            missing_resources = True
                            break
                            #raise Exception(f'{intervention_name} resources {k} missing day {str_day}')
                        usage_key = (resource_name, day)  # pair: (resource name, day) as key
                        resource_usage[usage_key] = v[str_day][str_day]
                    if missing_resources:
                        continue # one resource has no resources for a day
                    
                    # Resources needed by items in list for this day
                    for ans_name, ans_response in ans.items():
                        ans_day = ans_response["Day"]
                        ans_delta = ans_response["Delta"]
                        
                        if overlap([day, day+delta-1], [ans_day, ans_day+ans_delta-1]):
                            # An intervention in answer overlaps with current intervention
                            for resource_name, v_resource in ans_response["Resources"].items():
                                for overlap_day in range(day, day+int(delta)):
                                    # Get resource usage for each day of overlap
                                    usage_key = (resource_name, overlap_day)
                                    if not usage_key in resource_usage:
                                        resource_usage[usage_key] = 0
                                    resource_usage[usage_key] += v_resource
                    
                    # Check resource less than max
                    resources = data["Resources"]
                    for usage_key, value in resource_usage.items():
                        resource_name, overlap_day = usage_key  # values from tuple
                        if value > resources[resource_name]["max"][day-1]: # max value for resoure for this day
                            break
                    else:
                        # Resource didn't exceed max
                        # Check on Exclusion
                        winter = data["Seasons"]['winter']
                        summer = data["Seasons"]['summer']
                        isa = data["Seasons"]['is']
                        if str_day in winter:
                            season = "winter"
                        elif str_day in summer:
                            season = "summer"
                        elif str_day in isa:
                            season = "is"
                        else:
                            season = ""
                            
                        exclusions = data["Exclusions"]
                        bExclude = False
                        for k, v_lst in exclusions.items():
                            if season in v_lst and intervention_name in v_lst:
                                for intervention_k, ans_response in ans.items():
                                    if intervention_k in v_lst:
                                        ans_day = ans_response["Day"]
                                        ans_delta = ans_response["Delta"]
                                        if overlap([day, day+delta-1], [ans_day, ans_day+ans_delta-1]):
                                            bExclude = True
                                            break
                                if bExclude:
                                    break
                        if not bExclude:
                            # Resources used
                            response = {"Day": day, "Delta": intervention["Delta"][day-1]}
                            resources = {k:v[str_day][str_day] for k, v in intervention["workload"].items()}
                            response['Resources'] = resources
                            ans[intervention_name] = response
                            
                            result = allocate2(data, ans)
                            if result:
                                # was able to find an answer going forward using intervention
                                # on this day,so return the result
                                return result
                            # Remove last entry so we can try next iteration
                            del ans[intervention_name]
    

Usage

answer = allocate2(data)