Need help with problem 2b and 2c in the following question on Constraint Scheduling problem.

In this problem, you will leverage our CSP solver for the problem of course scheduling. We have scraped a subset of courses that are offered from Stanford's Bulletin. For each course in this dataset, we have information on which quarters it is offered, the prerequisites (which may not be fully accurate due to ambiguity in the listing), and the range of units allowed. You can take a look at all the courses in courses.json. Please refer to util.Course and util.CourseBulletin for more information.

To specify a desired course plan, you would need to provide a profile which specifies your constraints and preferences for courses. A profile is specified in a text file (see profile*.txt for examples). The profile file has four sections:

• The first section specifies a fixed minimum and maximum (inclusive) number of units you need to take for each quarter. For example:

  minUnits 0 maxUnits 3 

• In the second section, you register for the quarters that you want to take your courses in. For example,

  register Aut2019 register Win2020 register Spr2020 

  would sign you up for this academic year. The quarters need not be contiguous, but they must follow the exact format XxxYYYY where Xxx is one of Aut, Win, Spr, Sum and YYYY is the year.
• The third section specifies the list of courses that you've taken in the past and elsewhere using the taken keyword. For example, if you're in CS221, this is probably what you would put:

  taken CS103 taken CS106B taken CS107 taken CS109 

• The last section is a list of courses that you would like to take during the registered quarters, specified using request. For example, two basic requests would look like this:

  request CS224N request CS229 

  Not every request must be fulfilled, and indeed, due to the additional constraints described below, it is possible that not all of them can actually be fulfilled.

Constrained requests. To allow for more flexibility in your preferences, we allow some freedom to customize the requests:

• You can request to take exclusively one of several courses by specifying:

  request CS229 or CS229A or CS229T

  Note that these courses do not necessarily have to be offered in the same quarter. The final schedule can have at most one of these three courses. Each course can only be requested at most once.

• If you want to take a course in one of a specified set of quarters, use the in modifier. For example, if you want to take one of CS221 or CS229 in either Aut2018 or Sum2019, do:

  request CS221 or CS229 in Aut2018,Sum2019

  If you do not specify any quarters, then the course can be taken in any quarter.

• Another operator you can apply is after, which specifies that a course must be taken after another one. For example, if you want to choose one of CS221 or CS229 and take it after both CS109 and CS161, add:

  request CS221 or CS229 after CS109,CS161

  Note that this implies that if you take CS221 or CS229, then you must take both CS109 and CS161. In this case, we say that CS109 and CS161 are prereqs of this request. (Note that there's no space after the comma.)

  If you request course A and B (separately), and A is an official prerequisite of B based on the CourseBulletin, we will automatically add A as a prerequisite for B; that is, typing request B is equivalent to request B after A. Note that if B is a prerequisite of A, to request A, you must either request B or declare you've taken B before.

• Finally, the last operator you can add is weight, which adds non-negative weight to each request. To accommodate this, we will work with a standard CSP (as opposed to unweighted, like Problem 1), which associates a weight for each assignment x based on the product of m factor functions f1,,fm:

  Weight(x)=j=1mfj(x)

  where each factor fj(x)0. Our goal is to find the assignment(s) x with the highest weight. Notice that our backtracking search already works with normal CSPs; you should simply define factors that output real numbers. For CSP construction, you can refer to the CSP examples we have provided in util.py for guidance (create_map_coloring_csp() and create_weighted_csp()).

  All requests have a default weight value of 1. Requests with higher weight should be preferred by your CSP solver. Note that you can combine all of the aforementioned operators into one as follows (again, no space after comma):

  request CS221 or CS229 in Win2018,Win2019 after CS131 weight 5

Each request line in your profile is represented in code as an instance of the Request class (see util.py). For example, the request above would have the following fields:

• cids (course IDs that you're choosing one of) with value ['CS221', 'CS229']
• quarters (that you're allowed to take the courses) with value ['Win2018', 'Win2019']
• prereqs (course IDs that you must take before) with value ['CS131']
• weight (preference) with value 5.0

It's important to note that a request does not have to be fulfilled, but if it is, the constraints specified by the various operators after,in must also be satisfied.

You shall not worry about parsing the profiles because we have done all the parsing of the bulletin and profile for you, so all you need to work with is the collection of Request objects in Profile and CourseBulletin to know when courses are offered and the number of units of courses.

Well, that's a lot of information! Let's open a python shell and see them in action:

import util # load bulletin bulletin = util.CourseBulletin('courses.json') # retrieve information of CS221 cs221 = bulletin.courses['CS221'] print(cs221) # look at various properties of the course print(cs221.cid) print(cs221.minUnits) print(cs221.maxUnits) print(cs221.prereqs) # the prerequisites print(cs221.is_offered_in('Aut2018')) print(cs221.is_offered_in('Win2019')) # load profile from profile_example.txt profile = util.Profile(bulletin, 'profile_example.txt') # see what it's about profile.print_info() # iterate over the requests and print out the properties for request in profile.requests: print(request.cids, request.quarters, request.prereqs, request.weight) 

Solving the CSP. Your task is to take a profile and bulletin and construct a CSP. We have started you off with code in SchedulingCSPConstructor that constructs the core variables of the CSP as well as some basic constraints. The variables are all pairs of requests and registered quarters (request, quarter), and the value of such a variable is one of the course IDs in that Request or None, which indicates none of the courses should be taken in that quarter. We will add auxiliary variables later. We have also implemented some basic constraints: add_bulletin_constraints(), which enforces that a course can only be taken if it's offered in that quarter (according to the bulletin), and add_norepeating_constraints(), which constrains that no course can be taken more than once.

You should take a look at add_bulletin_constraints() and add_norepeating_constraints() to get a basic understanding how the CSP for scheduling is represented. Nevertheless, we'll highlight some important details to make it easier for you to implement:

• The existing variables are tuples of (request, quarter) where request is a Request object (like the one shown above) and quarter is a str representing a quarter (e.g. 'Aut2018'). For detail please look at SchedulingCSPConstructor.add_variables().
• The domain for quarter is all possible quarters (self.profile.quarters, e.g. ['Win2016', 'Win2017']).
• Given a course ID cid, you can get the corresponding Course object by self.bulletin.courses[cid].

1. [6 points] Implement the function add_quarter_constraints() in submission.py. This is when your profile specifies which quarter(s) you want your requested courses to be taken in. This is not saying that one of the courses must be taken, but if it is, then it must be taken in any one of the specified quarters. Also note that this constraint will apply to all courses in that request.
2. [10 points] Let's now add the unit constraints in add_unit_constraints().
   1. In order for our solution extractor to obtain the number of units, for every course, you must add a variable (courseId, quarter) to the CSP taking on a value equal to the number of units being taken for that course during that quarter. When the course is not taken during that quarter, the unit should be 0.
   2. You must take into account the appropriate binary factor between (request, quarter) and (courseId, quarter) variables.
   3. You must ensure that the sum of units per quarter for your schedule are within the min and max threshold, inclusive. You should use the create_sum_variable() function we've implemented for you; pay careful attention to the arguments.

   Hint: If your code times out, your maxSum passed to create_sum_variable() might be too large.

   Note: Each grader test only tests the function you are asked to implement. To test your CSP with multiple constraints you can add to the profile text file whichever constraints that you want to add and run run_p2.py. Here is an example with profile2b.txt as input:

   python run_p2.py profile2b.txt 

   Running this command will print information that may be helpful for debugging, such as profile information, the number of optimal assignments found (along with their weight and the number of times backtrack() is called while solving the CSP), one full optimal assignment, and the resulting course schedule.
3. [2 points] Now try to use the course scheduler for any two quarters in the future (or more quarters if you wish, although this might lead to a slower search). Create your own profile.txt (take a look at some of the profile text files included in the assignment's main directory for inspiration) and then run the course scheduler:

   python run_p2.py profile.txt 

   If the courses you wish to schedule are not listed in courses.json, feel free to add them in as you please! In addition, feel free to modify course details as well (e.g., you can change the list of quarters that a course is being offered in if it does not match the information on the current year's course calendar). You might want to turn on the appropriate heuristic flags to speed up the computation; in particular, self.ac3 = True applies the arc-consistency heuristic that we implement for you, and you can use your own MCV implementation. Does it produce a reasonable course schedule? Please include your profile.txt and the best schedule in your writeup (you can just paste it into the pdf that you submit); we're curious how it worked out for you! Please include your schedule and the profile in the PDF; otherwise you will not receive credit.