Lesson Resource Allocation Problem - Artificial Intelligence - ثالث ثانوي

5. Optimization & Decision-making Algorithms In this unit, you will study various algorithms and techniques for finding the most efficient solutions to complex optimization problems. You will learn how optimization and decision-making algorithms work and how they can be applied to solve real-world problems related to resource allocation, scheduling, and route optimization. istry of Education 250 2024-1446 Learning Objectives In this unit, you will learn to: > Classify optimization approaches to address complex problems. > Describe different decision-making algorithms. > Use Python to solve team-based resource allocation problems. > Solve scheduling problems by using optimization algorithms. > Use Python to solve scheduling problems. > Use mathematical programming to solve optimization problems. > Define the Knapsack problem. > Define the Traveling Salesman problem. Tools > Jupyter Notebook

11 Lesson 1 Resource Allocation Problem Link to digital lesson www.ien.edu.sa Optimization Algorithms in Al Al is being used in various industries to make decisions that are efficient and accurate. One way Al is used to make decisions is through the use of machine learning algorithms. As you learned in the previous unit, machine learning algorithms enable Al to learn from data and make predictions or recommendations. For example, in health care, Al can be used to predict patient outcomes and recommend treatment plans based on data collected from similar cases. In finance, Al can be used to make investment decisions by analyzing large sets of financial data and identifying patterns that indicate potential risks or opportunities. Even though machine learning algorithms are increasingly popular, they are not the only type of Al algorithm that can be used to make decisions. Another approach is to use optimization algorithms, which are generally used to find the best solution to a problem based on certain constraints and objectives. Constraints Constraints are restrictions on the solution, such as a maximum weight limit for a package being shipped. Objective Functions Objective functions are measures of how well the solution meets desired outcomes, such as minimizing the travel distance for a delivery truck. The purpose of optimization is to achieve the "best" design relative to a set of prioritized criteria or constraints. These include maximizing factors such as productivity, reliability, longevity and efficiency, and at the same time, minimizing other factors such as costs, waste, downtime, and errors. Allocation Problems Allocation problems are common optimization problems in which a set of resources, such as workers, machines, or funds, need to be assigned to a set of tasks or projects in the most efficient way possible. They arise in a wide range of fields, including manufacturing, logistics, project management, and finance, and can be formulated in various ways depending on their constraints and objectives. In this lesson, you will learn about allocation problems and the optimization algorithms used to solve them. 1111 وزارة التـ Ministry of Education 024-446 Constraint Weight limitation WE Objective function Maximizing the number of items processed and dispatched Figure 5.1: Using optimization algorithms in a warehouse 251

Next, you will look at a number of examples, each with their own domain specific constraints and objectives. Transportation companies Airline scheduling Bad Manufacturers ☐ ☐ ☐ Inventory management in companies Power companies وزارة التعليم Ministry of Education 2024-1446 Constraints - Time windows for deliveries, to ensure that packages are delivered within a specific time frame. - The availability and capacity of delivery vehicles, to make sure that the right vehicle is used for each delivery and that it can carry the necessary amount of packages. - The availability and shift patterns of drivers and other employees, to ensure that they work efficiently and are not overworked. - Aircraft availability and maintenance schedules, to ensure that all airplanes are well-maintained and available for flights. - Air traffic control restrictions, to avoid delays and reduce fuel consumption. - Passenger demand and preferences, to schedule flights that are convenient for passengers. - Production capacity and lead times, to ensure that products are produced on time. - Material availability and storage capacity, to avoid stockouts or overstocking. - Demand fluctuations, to adjust production schedules based on changes in customer demand. - Limited storage capacity, which requires careful management of inventory levels. - Delivery lead times and variability, which affect how much inventory needs to be held at any given time. - Budget availability for purchasing inventory. - Electricity demand and fluctuations. - The availability of necessary raw materials and energy sources. - Transmission and distribution constraints, such as grid capacity and distance between power plants and consumers. Objective functions - Minimizing delivery time and distance traveled to reduce costs and improve efficiency. - Maximizing the number of packages delivered per vehicle to reduce the number of trips needed. Maximizing customer satisfaction by delivering packages on time and within a specified time frame. - Minimizing flight delays and cancellations to improve customer satisfaction. Maximizing aircraft utilization to reduce costs and improve efficiency. Maximizing revenue by offering flights that are in high demand and adjusting ticket prices based on demand. Minimizing production costs by optimizing the use of resources and reducing waste. - Maximizing production efficiency by scheduling production runs to minimize setup times and changeovers. - Maximizing customer satisfaction by ensuring products are available when needed. - Maximing profit by securing sufficient inventory levels for high-margin items. - Minimizing storage costs by optimizing inventory levels based on demand forecasts. Maximizing customer satisfaction by ensuring that the right products are available at the right time and at the right location, and by minimizing stockouts, delays, and other disruptions that can impact the customer experience. Minimizing the cost of generating and distributing electricity by optimizing the use of resources. - Minimizing power losses and service failures.

All of the above applications can be modeled as complex problems with a vast number of possible solutions. For instance, consider a classic resource-allocation problem focused on team formation. This problem arises when we have: • a large pool of workers with different skill sets, and • a task that requires a specific subset of skills in order to be completed. The objective is to create the smallest possible team of workers, while satisfying the constraint that the members of the team should be able to collectively cover all the skills required by the task. For instance, assume a simple scenario with five workers: Worker 1 Skills: s1, s3, s6 Worker 2 Skills: s2, s3 Worker 3 Skills: s1, s2, s3 Worker 4 Skills: s2, s4 Worker 5 Skills: s5 The task to be completed requires all skills s1, s2, s3, s4, s5, and s6. A brute-force solution would be to consider all possible teams of workers, focus on the teams that cover all required skills, and choose the team with the smallest size. Assuming that each team must have at least one person, you can create a total of 31 different teams with 5 workers. Brute-force Brute-force is a method of problem-solving that involves systematically trying every possible solution to the problem in order to find the optimal solution, regardless of computational cost. • For a team of size 1, there are 5 ways to choose 1 out of 5 workers. • For a team of size 2, there are 10 ways to choose 2 out of 5 workers. • For a team of size 3, there are 10 ways to choose 3 out of 5 workers. • For a team of size 4, there are 5 ways to choose 4 out of 5 workers. • For a team of size 5, there is only 1 way to choose all 5 workers. Evaluating all 31 possible teams would reveal that the best possible solution is creating a team that includes workers 1, 4 and 5. That team would cover all six required skills and would include three workers. It is not possible to cover all the skills with a smaller team, making this the optimal solution. Another solution would be a team that includes workers 1, 2, 3, and 5. While this team indeed covers all six skills, it also requires more •••workers. This makes it a feasible ..but suboptimal solution. Worker 1 Skills: s1, s3, s6 The total number of possible different teams you can create is: 5 + 10 + 10 + 5 + 1 = 31 The number can also be computed as 25 - 1. M Worker 1 Skills: s1, s3, s6 Worker 4 Skills: s2, s4 Worker 5 Skills: s5 Worker 2 Skills: s2, s3 Worker 3 Skills: s1, s2, s3 Worker 5 Skills: s5 وزارة التعليم Ministry of Education 2024-1446 253

The exhaustive nature of the brute-force approach guarantees that it will always find the optimal solution, as long as one exists. However, examining all possible teams comes at a high computational cost: • If we have 6 workers, the number of possible teams is 26-1 = 63 • If we have 10 workers, the number of possible teams is 210 - 1 = 1,023 • If we have 15 workers, the number of possible teams is 215 - 1 = 32,767 • If we have 20 workers, the number of possible teams is 220 - 1 = 1,048,575 • If we have 50 workers, the number of possible teams is 250 - 1 = 1,125,899,906,842,623 Clearly, in many settings, exhaustive enumeration of all possible solutions is not a practical option. Various optimization approaches have been proposed to address complex problems by searching the space of possible solutions in ways that are much more efficient than the brute-force approach. These approaches can be broadly classified into three categories: ⚫ heuristic methods • constraint programming • mathematical programming Optimal Solution Even for a modest number of 50 workers, the number of possible teams explodes to over one quadrillion! It is possible for multiple optimal solutions to exist. In this example, this would mean multiple teams that include three members and can cover all required skills. It is also possible that no feasible solution exists for some problems. For example, if the given task required a skill s7 that none of the workers possessed, then there would be no feasible solution. Heuristic Methods Heuristic methods are typically based on experience, rules of thumb, or common sense, rather than on a rigorous mathematical analysis. They can be used to find good solutions quickly, but do not guarantee an optimal (best possible) solution. Examples of heuristics include greedy algorithms, simulated annealing, genetic algorithms, and ant colony optimization. These methods are typically used for complex problems in which the computation time is too high and finding exact solutions is not feasible. You will learn more about these algorithms in the following lessons. Constraint Programming Constraint Programming (CP) solves optimization problems by modeling the constraints and finding a solution that satisfies all the constraints. This approach is particularly useful for problems that have a large number of constraints or that require the optimization of several objectives. + Pros Heuristics are computationally efficient, can handle complex problems, and can find good quality solutions if a reasonable heuristic is used. - Cons They do not guarantee an optimal solution and some heuristics require significant tuning to deliver good results. + Pros CP can handle complex constraints and can find optimal solutions. - Cons These methods can also be computationally expensive for large problems. وزارة التعليم Ministry of Education 254 2024-1446

Mathematical Programming Mathematical Programming (MP) is a family of techniques that uses mathematical models to solve optimization problems. MP includes Linear Programming, Quadratic Programming, Nonlinear Programming, and Mixed-Integer Programming. These techniques are widely used in many areas, including economics, engineering, and operations. research. MP techniques also play a crucial role in deep learning. Deep learning models typically have a large number of parameters that need to be learned from data. Optimization algorithms are used to adjust the parameters of the model in order to minimize a cost function that measures the difference between the predicted output from the model and the true output. Several optimization algorithms, such as Adam, AdaGrad, and RMSprop have been developed specifically for deep learning models. + Pros MP can handle a wide range of optimization problems and can often guarantee an optimal solution. - Cons The computational cost for large problems and the complexity of creating an appropriate mathematical formulation are high for complex real-world problems. A Working Example: Optimization for the Team-Formation Problem This lesson will initially demonstrate the use of a brute-force algorithm and a greedy heuristic algorithm for solving a decision problem focused on the team-based resource allocation problem described above. Then, the results of the two algorithms will be compared. The following function can be used to create randomized instances of the team formation problem. It allows the user to specify four parameters: the total number of skills to be considered, the total number of available workers, the number of skills that the members of a team have to collectively cover in order to complete a task, and the maximum number of skills that each worker can have. The function then creates and returns a set of workers with different skillsets, as well as the set of required skills. The function uses the popular "random" library, which can be used to sample random numbers from a given interval or random elements from a given list. Greedy Heuristic Algorithm A greedy algorithm is a heuristic approach to problem-solving, where the algorithm constructs the solution step-by-step, selects the locally optimal choice at each stage, hoping to eventually reach a global optimum. import random def create_problem_instance(skill_number, # total number of skills worker_number, # total number of workers required_skill_number, #number of skills the team has to cover max_s k_skills_per_worker #max number of skills per worker ): # creates the global list of skills s1, s2, s3, ... skills ['s' + str(i) for i in range(1, skill_number+1)] worker_skills = dict() # dictionary that maps each worker to their set of skills وزارة التعليم Ministry of Education 2024-1446 255

for i in range(1, worker_number+1): # for each worker # makes a worker id (w1, w2, w3, ...) worker id = 'w' + 'w' + str(i) # randomly decides the number of skills that this worker should have (at least 1) my_skill_number = random.randint(1, max_skills_per_worker) # samples the decided number of skills my_skills = set(random.sample(skills, my_skill_number)) # remembers the skill sampled for this worker worker_skills [worker_id] = my_skills # randomly samples the set of required skills that the team has to cover required skills = set(random.sample(skills, required_skill_number)) # returns the worker and required skills return {'worker_skills': worker_skills, 'required_skills': required_skills} Now, you will test the above function by creating a problem instance with 10 total skills, 6 workers, 5 required skills, and at most 5 skills per worker. وزارة التعليم Ministry of Education 256 2024-1446 x10 The problem needs 10 total skills x6 workers x5 required skills x5 at most 5 skills per worker Figure 5.2: Graphic representaion of a problem instance Given the randomized nature of the function, you will get a different problem instance every time you run this code.

# the following code represents the above test sample_problem = create_problem_instance(10, 6, 5, 5) # prints the skills for each worker for worker_id in sample_problem['worker_skills']: print(worker_id, sample_problem['worker_skills'][worker_id]) print() # prints the required skills that the team has to cover print('Required Skills:', sample_problem [ 'required_skills']) w1 {'s10'} w2 {'s2', 's8', 's5', 's6'} w3 {'s7', 's2', 's4', 's5', 's1'} W4 {'s9', 's4'} w5 {'s7', 's4'} w6 {'s7', 's10'} Required Skills: {'s6', 's8', 's7', 's5', 's9'} The next step is to create a solver which is an optimization algorithm that can determine the smallest possible team of workers that can be used to cover all the required skills. Decision Making with a Brute-Force Algorithm The first solver will implement the brute-force approach that relies on exhaustively enumerating and considering all possible teams. This solver will use the "combinations" tools from the "itertools" module to generate all possible teams of a specific size. The tool is demonstrated via a simple example below: # used to generate all possible combinations in a given list of elements from itertools import combinations L = ['w1', 'w2', 'w3', 'w4'] print('pairs', list(combinations(L, 2))) # all possible pairs print('triplets', list(combinations (L, 3))) # all possible triplets pairs [('w1', 'w2'), ('w1', 'w3'), ('w1', 'w4'), ('w2', 'w3'), ('w2', 'w4'), ('w3', 'w4')] triplets [('w1', 'w2', 'w3'), ('w1', 'w2', 'w4'), ('w1', 'w3', 'w4'), ("'W2, 'W3', 'W4')] وزارة التعليم Ministry of Education 2024-1446 257

The following function can then be created to solve an instance of the team formation problem via the brute-force approach. This brute-force solver considers all possible team sizes and creates all possible teams for each size. It then identifies teams that cover all required skills and reports the smallest one. def brute force_solver (problem): worker_skills = problem['worker_skills'] required skills = problem [ 'required_skills'] required_skills worker ids = list(worker_skills.keys()) # gets the ids of all the workers worker_num = len(worker_ids) # total number of workers all possible_teams = [] # remembers all possible teams best team = None #remembers the best (smallest) team found so far # for each possible team size (singles, pairs, triplets, ...) for team_size in range(1, worker_num+1): # creates all possible teams of this size teams = combinations (worker_ids, team_size) for team in teams: # for each team of this size skill_union = set() #union of skills covered by all members of this team for worker_id in team: # for each team member #adds their skills to the union skill_union.update(worker_skills [worker_id]) # if all the required skills are included in the union if required_skills.issubset(skill_union): # if this is the first team that covers all required skills # or this team is smaller than the best one if best team == None or len(team) < len(best_team): team #makes this team the best one best_team = return best_team # returns the best solution It is possible for a problem instance to not have a feasible solution. For example, if the set of required skills includes a skill that none of the available workers possesses, then there is no way to create a team that covers all skills. In such cases, the above solver will simply return a None value. The following code can now be used to test the brute-force solver on the sample problem that was created above. # uses the brute-force solver to find the best team for the sample problem best team brute force_solver (sample_problem) = print(best_team) '('W2', w3', 'W4') وزارة التعليم Ministry of Education 258 2024-1446

The brute-force solver is guaranteed to always find the best possible solution (the smallest possible team), as long as a solution exists. However, as discussed in the beginning of this Lesson, its exhaustive nature also leads to an explosion of computational cost as the size of the problem gets bigger. This can be demonstrated by creating multiple problems with an increasing number of workers. The following code can be used to generate instances of the team formation problem. The number of workers is varied to be equal to 5, 10, 15, and 20. A total of 100 instances are generated for each worker number. All instances include 10 total skills, 8 required skills and at most 5 skills per worker. problems_with_5_workers = [ ] # 5 workers problems_with_10_workers = [] # 10 workers problems_with_15_workers = [] # 15 workers problems_with_20_workers = [ ] # 20 workers for i in range(100): # repeat 100 times problems_with_5_workers.append(create_problem_instance(10, 5, 8, 5)) problems_with_10_workers.append(create_problem_instance(10, 10, 8, 5)) problems_with_15_workers.append(create_problem_instance(10, 15, 8, 5)) problems_with_20_workers.append(create_problem_instance(10, 20, 8, 5)) The following function accepts a list of problem instances and a solver. It then uses the solver to compute and returns the solution for all instances. It also prints the total time (in seconds) required to compute the solutions, as well as the total number of instances for which a solution could be found. import time def gets_solutions (problems, solver): total_seconds = 0 # total seconds required to solve all problems with this solver total_solved = 0 # total number of problems for which the solver found a solution solutions = [ ] # solutions returned by the solver for problem in problems: start_time best team end time = time.time() # starts the timer solver (problem) # computes the solution time.time() # stops the timer solutions.append(best_team) # remembers the solution total_seconds += end_time-start_time #computes total elapsed time if best team != None: # if the best team is a valid team total_solved += 1 print("Solved {} problems in {} seconds".format(total_solved, وزارة التعليم Ministry of Education 2024-1446 return solutions total_seconds)) 259

The following code uses this function and the brute-force solver to compute the solutions for 5-worker, 10-worker, 15-worker, and 20-worker datasets that were created above. brute solutions_5 = gets_solutions (problems_with_5_workers, brute_force_solver) solver = brute_solutions_10 = gets_solutions (problems_with_10_workers, brute_force_solver) solver = brute_solutions_15 = gets_solutions (problems_with_15_workers, solver brute_force_solver) = brute_solutions_20 = gets_solutions (problems_with_20_workers, brute_force_solver) solver = Solved 23 problems in 0.0019948482513427734 seconds Solved 80 problems in 0.06984829902648926 seconds Solved 94 problems in 2.754629373550415 seconds Solved 99 problems in 109.11902689933777 seconds While the exact numbers printed by the gets_solutions() function will vary due to the randomized nature of the datasets, two patterns will always be consistent: . Increasing the number of workers leads to a higher number of problem instances for which a solution could be found. This is reasonable, as having more workers increases the probability that the worker pool includes at least one worker that possesses each required skill. • Increasing the number of workers leads to a significant (exponential) increase in computational time. This was anticipated given the analysis conducted in the beginning of this lesson. For worker populations of size 5, 10, 15, and 20, the number of possible teams is equal to 31, 1023, 32767, and 1048575, respectively. In general, given N workers, the number of possible teams is equal to 2N-1. This number becomes far too large to evaluate even for modest values of N. This demonstrates that, even for a simple problem with 1 constraint (covering all required skills) and 1 objective (minimizing the size of the team), brute force is only applicable for very small datasets and it is certainly not practical for any of the complex real-world optimization problems described at the beginning of this lesson. Decision Making with a Greedy Heuristic Algorithm The following function addresses this constraint by implementing an optimization algorithm based on a "greedy" heuristic. The heuristic gradually populates a team by adding one member at a time. The next member that is added is always the one that covers the most of the previously uncovered skills. The process continues until all required skills have been covered. The "greedy heuristic" in this case is the criterion of choosing a worker that covers the most of the previously uncovered skills. A different heuristic function could have been adding first the worker having the largest number of skills. وزارة التعليم Ministry of Education 260 2024-1446

def greedy_solver(problem): worker_skills = problem['worker_skills'] required skills = problem['required_skills'] # skills that still have not been covered uncovered_required_skills = required_skills.copy() best team = [] # remembers only the skills of each worker that are required but haven't been covered yet uncovered_worker_skills = {} for worker_id in worker_skills: # remembers only the required uncovered skills that this worker has uncovered_worker_skills [worker_id] = worker_skills[worker_id]. intersection(uncovered_required_skills) # while there are still required skills to cover while len(uncovered_required_skills) > 0: best_worker_id = None # the best worker to add next # number of uncovered skills required for the best worker to cover best_new_coverage = 0 for worker_id in uncovered_worker_skills: #uncovered required skills that this worker can cover intersection() returns a new set containing only the skills that are common to worker's worker_skills and uncovered_required_skills. my_uncovered_skills = uncovered_worker_skills [worker_id] # if this worker can cover more uncovered required skills than the best worker so far if len(my_uncovered_skills) > best_new_coverage: best_worker_id=worker_id # makes this worker the best worker best_new_coverage=len (my_uncovered_skills) if best_worker_id != None: # if a best worker was found best team.append(best_worker_id) # adds the worker to the solution # removes the best worker's skills from the skills to be covered uncovered_required_skills = uncovered_required_skills - uncovered_worker_skills [best_worker_id] for worker_id in uncovered_worker_skills: # remembers only the required uncovered skills that this worker has uncovered_worker_skills [worker_id] = uncovered_worker_skills [worker_id].intersection (uncovered_required_skills) else: # no best worker has been found and some required skills are still uncovered return None # no solution could be found return best_team وزارة التعليم Ministry of Education 2024-1446 261

The greedy solver does not consider all possible teams and does not guarantee finding the optimal solution. However, as demonstrated below it is much faster than the brute-force solver and can still produce good (and often optimal) solutions. The method is also guaranteed to find a solution if one exists. The following code uses the greedy solver to compute the solutions for the same 5-worker, 10-worker, 15-worker, and 20-worker datasets that was used to evaluate the brute-force solver. greedy_solutions_5 = gets_solutions(problems_with_5_workers, solver = greedy_solver) greedy_solutions 10 = gets_solutions (problems_with_10_workers, solver greedy_solver) = greedy_solutions_15 = gets_solutions (problems_with_15_workers, solver greedy_solver) = greedy_solutions_20 = gets_solutions (problems_with_20_workers, solver greedy_solver) = Solved 23 problems in 0.0009970664978027344 seconds Solved 80 problems in 0.000997304916381836 seconds Solved 94 problems in 0.001995086669921875 seconds Solved 99 problems in 0.0019943714141845703 seconds The difference in speed between the two solvers is evident. In fact, the greedy solver can be applied even on much larger problem instances. For example: # creates 100 problem instances of a team formation problem with 1000 workers problems_with_1000_workers [ ] for i in range(100): #repeats 100 times problems_with_1000_workers.append(create_problem_instance(10, 1000, 8, 5)) # solves the 100-worker problems using the greedy solver greedy_solutions_1000 = gets_solutions (problems_with_1000_workers, solver greedy_solver) = Solved 100 problems in 0.09574556350708008 seconds وزارة التعليم Ministry of Education 262 2024-1446

Comparing the Algorithms Having demonstrated the speed advantage of the greedy heuristic, the next step is to validate the quality of the solutions that it produces. The following function accepts the solutions produced by the greedy and brute-force solvers on the same collection of problem instances. It then reports the percentage of instances for which both solvers report the optimal solution (the smallest possible team). def compare(brute_solutions, greedy_solutions): total_solved = 0 same size = 0 same_size for i in range(len(brute_solutions)): if brute solutions[i] != None: # if a solution was found total_solved += 1 # if the solvers reported a solution of the same size if len(brute_solutions[i]) same_size += 1 == len(greedy_solutions[i]): return round(same_size / total_solved, 2) The compare() function can now be used to compare the effectiveness of the two solvers applied to the datasets with 5, 10, 15, and 20 workers. print(compare(brute_solutions_5,greedy_solutions_5)) print(compare(brute_solutions_10, greedy_solutions_10)) print(compare (brute_solutions_15, greedy_solutions_15)) print(compare (brute_solutions_20, greedy_solutions_20)) 1.0 0.82 0.88 0.85 The results demonstrate that the greedy heuristic can consistently find the optimal solution for about 80%, or higher, of all solvable problem instances. In fact, one can easily verify that, even for cases when it fails to find the optimal solution, the size of the team that it returns is very close to that of the best possible team. Combined with the overwhelming speed advantage, this makes the heuristic a far more practical choice for realistic applications. The next lesson will explore even more intelligent optimization techniques and their applications to different problems. وزارة التعليم Ministry of Education 2024-1446 263

Exercises 1 What are the advantages and disadvantages of the brute-force and greedy algorithms for solving optimization problems? 2 Analyze how greedy heuristic algorithms are used to find optimal solutions in optimization problems. وزارة التعليم Ministry of Education 264 2024-1446

3 You want to create a greedy solver for the optimization problem of team formation. Complete the following code so that the function utilizes a greedy heuristic for the assignment of team members to a job. def greedy_solver(problem): worker_skills-problem['worker_skills'] # worker skills for this problem required skills-problem['required_skills'] # required skills for this problem uncovered_required_skills = required_skills. best team=[] # best solution uncovered_worker_skills={} for worker_id in worker_skills: () # skills not covered uncovered_worker_skills[worker_id]=worker_skills[worker_id]. (uncovered_required_skills) while len(uncovered_required_skills) > 0: best_worker_id= # the best worker to add next best_new_coverage=0 #number of uncovered required skills covered by the best worker for worker_id in uncovered_worker_skills: # for each worker my_uncovered_skills-uncovered_worker_skills[worker_id] # if this worker can cover more uncovered required skills than the best worker so far len(my_uncovered_skills)>best_new_coverage: if best_worker_id=worker_id #makes this worker the best worker (my_uncovered_skills) best_new_coverage= if best_worker_id != : # if a best worker was found best_team. (best_worker_id) # adds the worker to the solution #removes the best worker's skills from the skills to be covered uncovered_required_skills=uncovered_required_skills - uncovered_ worker_skills [best_worker_id] # for each worker for worker_id in uncovered_worker_skills: # remembers only the required uncovered skills that this worker has uncovered_worker_skills [worker_id] = uncovered_worker_ skills [worker_id]. (uncovered_required_skills) else: # no best worker has been found and some required skills are still uncovered return return best_team # no solution could be found وزارة التعليم Ministry of Education 2024-1446 265

4 List three different real-world optimization problems. For each problem: • Give an example of an objective function. • Give two examples of constraints, if any. 5 In the brute-force solver, if you increase the number of workers, how does it affect the problem in terms of number of solutions and computational time? وزارة التعليم Ministry of Education 266 2024-1446