last day (24 days later) » 

3:14 PM
0
A: How to apply an enumeration algorithm into a problem?

DarrylGThis 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...

 
Thank you for your solutions. I will take a look.
Do you have any ideas if we have an objective function, is there any way to optimize it?
 
@Erwinwin--can you say more about the type of objective function? Backtracking is normally more of a search algorithm where the search has constraints. It's fast by quickly eliminating portions of the space that don't satisfy the constraints.
 
Maybe you can read about the objective here as I put the full file name A_08.json too for testing: gitlab.com/Schrodinger168/practice/-/tree/master/Objective
If you can purpose solutions for this optimization. Thank you so much for your help!
 
@Erwinwin--I'm not clear how an optimization function in the writeups apply to your problem. In your case in reduced the any solution that satisfied the constraints. Anyway, there are other linear and non-linear solvers. One is the Pulp as described here. However, it may be difficult to specify the constraints of this problem and I don't see where an optimization function comes in.
 
in fact, the goal is to find the minimum of obj with compose of obj1 and obj2. Still thanks for your approaches for at least generate for one solution that satisfied the constraint even if it is not an optimal one. but there is an error with instance A_03.json. I dont know why. Moreover, can you explain a bit clear for your function overlap?
 
3:14 PM
@Erwinwin--overlap checks to see if two interventions overlap in time. Overlap is used to 1) check resources used during the overlap, and 2) check exclusions during the overlap.
@Erwinwin--updated so it worked with file Objective_A_03.json. Issue was an error was erroring when an intervention is missing a resource entry for a day being tried (i.e. Intervention_102, Ressources_6, missing day "1". Fix was not allow intervention to be run on that day if resources are not defined.
 
Thank you so much DarryIG. I understood most part of your code but for some it seems a bit difficult to understand. Can you write a pseudo code or a picture illustration the flow of your algorithm. Thanks again for your help.
 
@Erwinwin--added pseudo code at end. Does this help? Are you familiar with generator functions? If not this can be done with regular functions but not as cleanly.
 
Thank you for your help again. I am new with generator function. With this pseudo code it might help more.
 
@Erwinwin--added a pseudo code for a normal function version. It only finds the first solution. The advantage of generator version is we could potentially keep calling net to get successive solutions.
 
It means that the generator function is more efficient than non-generator function right? but for the generator function it generates only the first solution just as like non-generate or what?
 
3:14 PM
@Erwinwin--the efficiency is about the same. With the generator function we only take the first solution since we only call next once. For the non-generator function we are only getting the first solution. We could add another argument i.e. solutions to the non-gnerator function which adds ans to solutions each time a solution is found. This may take a while to run since it won't return until it finds all the solutions. In the generator each time we call next, it returns after the next solution so we get intermediate results faster.
 
Thanks I understand better :)
 
@Erwinwin--actually generators use to be slower than regular functions (i.e. Python 2), but Python 3 made implementation improvements to make performance pretty similar. So now, its more of pick what's what's best for your problem which in this case I think are generator function (opinion). Notice with the generator version we didn't need the backtracking logic since the yield from .make it unnecessary.
 
Thank for the remark. In conclusion the generation and non-generation you used in your code are still in the backtracking algorithm right?
 
@Erwinwin--yes, they are both using the backtracking algorithm. By the way, it occurs to me that lazy sequences are one thing generators can do that regular functions can not.
@Erwinwin--this article on What is Depth First Search may explain backtracking more clearly.
 
Thanks for the supported resources. It will help me to improve my beginning level to solve this kind of problems. I really appreciate your help so far. God bless you :)
 
3:14 PM
@Erwinwin--glad to help. Good to be able to "pay it forward".
 
Well I just try to do sth with non-generator function. It seems does not work for me. I just try to avoid using yield and yield from because it seems so advance for me. Can you propose the full normal code without using generator function? I read a lot of things about yield as many it is useful for the problems containing a lot of nodes and make memory more efficient than using non-generator function but It just too advance for me at the moment.
 
@Erwinwin--added non-generator version (allocate2). You can return to generators later, but know they are another interesting tool and is Python's method for Lazy Evaluation.
 
Thank you for your non-generator function once again. I really disturb you a lot. I have one question related to resources verification. I still have doubt about your code because the result you print the resource_usage I saw you calculate only the first day of each intervention we are okay if the delta=1 but how about the other interventions that delta is not equal to 1 for example delta=2 I think we need to verify the resource of day two too but your code is just verify the first day no?
One more thing for testing the non-generator version I just change the answer = allocate2(data, None) right or change other things else?
 
@Erwinwin--the confusion may be because it's not clear how the for loops work with the recursion. The method is able to assign the first day that works for an intervention that is compatible with the previous interventions in the list. It tries days in the range for day in range(1, last_day+1):. It's basically looping through all combinations of assigning interventions to days, but during it in a way that's much faster since it avoids expanding on assignments that don't work.
@Erwinwin--For example if we have interventions 1 to N and we know that assigning interventions 1 & 2 to day 1 is incompatible. Is there any need to look at combinations assignments of interventions 3 to N which have interventions 1 & 2 assigned to day 1? Its analogous to chess (if you play)--if you know if you make a certain move, your opponent could checkmate you in 3 moves, is there any point in wasting time searching for other reasons the move is bad (i.e., other ways your opponent could beat you)?
@Erwinwin--yes, just change to answer = allocate2(data) (note: placing None is optional i.e. works either way since its the default). Called it allocate2 (i.e. different name) so you could try both methods.
 
To what I have understood so far for this problem. For example if you assign Intervention 1 to day 1 and resources it needs to use are: for example Resource_1 and Resource_2. The duration of that intervention for example delta = 2. It means if you start at day 1 you need to finish it at day 2 and for each day(day 1 and day 2) we need to calculate the (Resource_1 and Resource_2 for day 1) and the (Resource_1 and Resource_2 the same for day 2) and finally, maybe do the loop through all the Resource_X in the workload to see if each day one of the Resource_X not exceed or exceed its min and max?
Did your code just verify this? because I saw the code printed only the first day of its Resources usage and it is good if delta = 1 but if delta is not 1 example 2, 3.. we need to take into account the second third day.. and so on?
 
3:14 PM
@Erwinwin--take a look at the output for running file example1.json. Note that the start for Intervention_315 is day = 2 since it conflicts with some other interventions which start on day 1. So, it gives interventions different days in the case of conflicts or lack of resources.
 
Yes that one I understood because here Intervention_315 with Intervention_456 and Intervention_536 cannot start at the same day during winter. Also Intervention_315 and Intervention_415 cannot start at the same day during is. But The variable I want to focus here is Delta it is the duration of each intervention and the question is like what I said to you in the conversation above.
 
@Erwinwin--regarding the question above that's where the overlap function comes in. It determines if two interventions overlap in time considering the starting day and delta. Interventions which exclude each other in a season can't overlap. For resources, it currently sums up the resources by name that are used. Perhaps this should be a little more granular and sum up the resources by name, day? I'll check that.
 
Here what I want to say Intervention Intervention_31 Start day 1, Duration: 2.0 Resource: Ressources_3 Usage: 0.86 Resource: Ressources_4 Usage: 0.86 Resource: Ressources_9 Usage: 0.086 Ressources_3 _4 _9 you verify and print only the first day of the intervention but here Delta (Duration) is 2. So it means you did not verify the Ressources usage for the second day of intervention?
Thanks for your verification and I hope you understood well my question :)
My idea I think that if we can create lists of all Ressource_X for example take into account example1.json here X value from 1 to 9. nine types of resources. We create list Ressource_X=[] each list has length of T. each index correspond to each day. So when we start assigning the intervention for example1.json for example assigning Intervention_31 with Delta = 2 as we know that it used Ressource_3 _4 _9 for each list of those resources we need to assign the value of the resources correspond to each index(each day)
You can see here if you need more information about the workload gitlab.com/Schrodinger168/practice/-/blob/master/…
 
@Erwinwin--does it make sense that I simply evaluated resource usage by using the tuple (resource_name, day) where I make a tuple (i.e. pair) when it's in use. I accumulate resource usage over this pair. I then have to check that resource usage (by name) is never greater than the max value. Does it make sense? Its a simple change to the existing code. Does it same simpler than the list method you mention above?
 
Yes you can modified as you want. For me I just make sure that the Ressources_X you verify are good when Delta is not equal to 1. We need to verify everyday(= T index) of each of every Ressource_X if they are in the range of min and max of each Ressource_X
 
3:14 PM
@Erwinwin--I didn't use the min. What is it's purpose? Don't we just need to ensure the resources used are less than or equal to the max?
 
yes I think here min is not so important. so you can just verify if it does not exceed the max
 
3:29 PM
Good a moderator moved this to chat. I would have suggested this, but in the past when I tried with other posters it was not possible when their reputation was less than 20 points.
 
okay it is good then
 

  last day (24 days later) »