Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
Solved

# Precise Formulation

Posted on 2010-11-10
Medium Priority
722 Views
I'm trying to give a precise formulation for this constraint satisfaction problem:

Class scheduling: There is a fixed number of professors and classrooms, a list of classes to be offered, and a list of possible time slots for classes. Each professor has a set of classes that he or she can teach.
0
Question by:JCW2
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 16
• 14

LVL 32

Expert Comment

ID: 34108450
Givens:

P = number of professors
P_i = the i_th professor, where i=1..P

C = number of classes to be offered
C_j = the j_th class, where j=1..C

S_i = { C_k | k in [1..C], where C_k can be taught by P_i }

============

Unknown:
T_i = The time slot for the i_th class

============

Constraint:
Mutual Exclusion ... to be filled in ...
0

LVL 32

Expert Comment

ID: 34108625
My previous posts makes an implicit assumption about the duration of a class. If you wish to add more flexibility on this trait, then some adjustments to the post must be made.
0

Author Comment

ID: 34113607
Is this valid?:
{CK, TL | K in [ C1.. CK ], where CK can be taught by PI; L in [T1 .. TL ], where CK is taught during TL}
0

LVL 32

Expert Comment

ID: 34113794
Sorry, not familiar with your formal notation.
0

Author Comment

ID: 34115845

Subs.PNG
0

Author Comment

ID: 34116036
"This," referring to the post with the cryptic notation.
0

LVL 32

Expert Comment

ID: 34116053
For the solution set, don't you need a triplet S = {P_i, T_j, C_k | ... } ?
That is, the i-th professor teaches the k-th class in the j-th timeslot.
Goal: Maximize |S| subject to constraints.
=======

Notation Issues:
You wrote:
C_K where k in [C1 .. C_K]
Shouldn't C_K be C_k (case sensitive?)
And "k in [C1 .. C_K]" - shouldn't it be "k in [1..C]", since k is an index but C1 is a class.

=======
Constraints:
I know it is obvious that a professor cannot teach two different classes in the same time slot; but do you need to state this in your set of constraints?

Defining S_i as above, shouldn't S_i be part of your set of constraints? Using this notation may simplify the construction (but I don't think it is mandatory).
0

LVL 32

Expert Comment

ID: 34116081
I would list every constraint first in simple English including all the obvious constraints (especially uniqueness and mutual exclusion). For example, a class cannot be in two different timeslots, and a class cannot be taught by two different professors.
0

Author Comment

ID: 34117027
Is this better:
Correction-2.PNG
0

LVL 32

Expert Comment

ID: 34117247
Doesn't http:#34117027 allow two classes to be in the same time slot? That would be OK if there were multiple classrooms.

If precision is necessary, then all assumptions (e.g., number of classrooms, fixed duration of classes and timeslots, etc.) probably should be stated as a preface to your set.

You also need to define what S is. Is S "all possible solutions"? If not, do you need to define "all possible solutions"?

In your OP, you use the term "lists". These lists are objects that can have their own symbol. I would think that more succinct notation would refer to these list symbols rather than using phrases like "can be taught by". In set notation, you can say x element of A (where A can be a list).

BTW - I forget notation, but should the triplet by enclosed in parens like:
(Ck, Tl, Pi) ? That way, it looks like a point in the 3d vector space. Then predefine the meaning of (Ck, Tl, Pi) as Pi teaches Ck in timeslot Tl. After defining this vector definition, it is not necessary to repeat it in your constraint definition as it is pre-defined. Then you can focus on just the constraints.

For constraints, you can use indexes like i != j to establish constraint relationships amongst the vectors.

0

Author Comment

ID: 34117259
Improved:
Solution-3.PNG
0

LVL 32

Expert Comment

ID: 34117303
>> "and a Ck occupies 1 Tl slot at a time"
If Ck were to occupy two timeslots at the same time, then that would perhaps be a redundancy (which depending upon notation can occur in schools).

But the issue is whether two different Ck can occupy the same timeslot. Anser is "No", I think. Is that in your set of constraints?

(If I misunderstood your intent here, then either I am being too fussy, or too tired, or the notation needs to follow a formalism that is not subject to misinterpretation, or all of the above. Back in 1-2 hours.)

In the meantime, could you write down the set of assumptions, and a simple set of constraints in layman's terms, and then we can check off the list a little easier.
0

Author Comment

ID: 34117358
C: Class; T: Time slot; P: Professor; K: index for Class; L: index for time slot; I: index for professor.
Solution-4.PNG
0

Author Comment

ID: 34117371
is this better:
S.PNG
0

LVL 32

Expert Comment

ID: 34117440
>> Tl teaches 1 Ck at a time
Having some trouble understanding this. Review this and see if you need to rephrase.

What is your precise definition of the set, S? Depending upon your definition, can C3, for example, appear more than once in S?

[C1..Ck] - if you left out this list and the other list, [T1..TL], would anything be missed? "where Ck can be taught by Pi in TL" - would this be a fair replacement?

While I don't agree with all of your notation (see my previous posts), at least I understand what I think you are trying to say; so maybe it is fine for your course.
0

Author Comment

ID: 34125452
I've overhauled my response. Is this any better:
ASet.PNG
0

LVL 32

Expert Comment

ID: 34128257
>> list: fixed number of professors,                {P}
>> list: fixed number of classrooms,               {D} // easier on the eyes to use {R} for the list of available rooms
>> list: fixed number of classes to be offered, {C}
>> list: fixed number of time slots for classes, {T}

From your OP, it seems that there are the four above lists. I think your "There is a finite number..." is saying this, but I'm not sure what the != 0 at the end means. Does it mean that each list is non-empty? IMO, I think your constraints do not need to restate the pre-conditions of the type and fixed-length of each list. But they

>> a list of possible time slots for classes
Is this just a list of time slots, or does each class get its own list of potential timeslots?

>> For 2 different P (professors) ...
I would break this up into two separate constraints. I am not sure what you mean by two different professors do not teach in a conflicting T (timeslot). Please help me understand using simple sentences, and then later formalize it.

On formalization, for your assignement, is it acceptable that your constraints be written in sentences as you have done in your last post, or are you required in the end to use notation such as, for example:
"For 2 different P (professors)" becomes "for Pi, Pj, where i != j"

For your definition of S, could you explain exactly what the set of elements in S represent. As mentioned before, this could be an issue to resolve. Do you need to define a set where each element of the set is one of the many scheduling solultions that satisfy the constraints? If so, do you think S is this set?

p.s. - fyi, my computer has hard disk problems so I'm borrowing another computer as it becomes available, so it may take awhile to get back to your responses. Sorry about that. BTW, if you could type in the answer, it will be easier for me to cutNpaste. For subscripts, you could write, for example, Pi or P_i.
0

LVL 32

Expert Comment

ID: 34128266
Hit submit to soon..
>> IMO, I think your constraints do not need to restate the pre-conditions of the type and fixed-length of each list. But the definitions and pre-conditions should be stated before you write out your constraints.
0

Author Comment

ID: 34129096
On English vs. mathematic notation, I think I should use as much notation as is practical.
0

Author Comment

ID: 34129245
Could you help me with the notation? Another thing; I think it would be good to use two time slot variables:

something like - P_A and P_B are in conflicting time slots if the time from T1_A to T2_A and T1_B to T2_B overlap.
0

LVL 32

Expert Comment

ID: 34129511
On notation, let the set U be the universe of all 4-tuples of {P, C, T, R}, where P, C, T, R are lists of professors, etc. A point in this Universe is (Pi, Cj, Tk, Rm), where i in {1..|P|}, j in {2...}, etc. Then, |U| = i*j*k*m. Obviously, most of these points do not satisfy your constraints.

From this I can think of two sets of interest (but not necessarily both needed). One is the set of all possible scheduling solutions. If you need this, then what would a single point in this set be? Keep in mind that a single point in U is just that a specific prof teaches a specific class in a specific room in a specific timeslot.

Another set is to define a set of points in U such that they satisfy the constraints.

Is it a fair assumption to say that all the courses are of equal length? (If so, this simplifies the problem).

In my previous few posts, I asked some questions; but I didn't get a response for some of them. Could you take the time to copy the question and give me your response. Sometimes a question is guidance; sometimes it is that I don't understand something you wrote. So, it would be useful if I were on the same page as you. Right now, I don't know where you agree or take issue with some of my posts.
0

Author Comment

ID: 34129547
On constraint satisfaction, I found the following:

http://4c.ucc.ie/web/outreach/tutorial.html

According to my text,

"A constraint satisfaction problem consists of three components, X, D, and C:
X is a set of variables, {X_1, ..., X_n}
D is a set of domains, {D_1, ..., D_n}, one for each variable.
C is a set of constraints that specify allowable combinations of values"

I'll be attending to your questions as soon as possible.
0

Author Comment

ID: 34129613
I put in the above comment because I thought it might help things along.

I'm confused as to why S_i should be part of my constraints.

"I know it is obvious that a professor cannot teach two different classes in the same time slot; but do you need to state this in your set of constraints?"

Unless I'm saying they juggle 2 or more classes at once, I think yes.

"You also need to define what S is. Is S 'all possible solutions'? If not, do you need to define 'all possible solutions'?"

Do you think stating "where S = all possible solutions" would work?

"Does it mean that each list is non-empty?"

Yes.

"Is this just a list of time slots, or does each class get its own list of potential timeslots?"

This variable was constrained or was supposed to be constrained by the professors.

"Is it a fair assumption to say that all the courses are of equal length?"

No.

What do you mean by "|U| = i*j*k*m"?

"Depending upon your definition, can C3, for example, appear more than once in S?"

There might be more than one professor teaching math.

0

LVL 32

Expert Comment

ID: 34129616
Then let X = set of variables, {X_1, ..., X_n} == {P, C, T, R}
D_1 = {P1, ... P_np}, where np = # professors
D_2 = {C1, ... C_nc}, where nc = # classes
etc.

The first constraint is explicitly in your OP:
>> Each professor has a set of classes that he or she can teach.
One way to represent this is a matrix, PC, having np rows, nc columns, with cells (PC_ij)being true/false. Another way is to define a class list for each Pi. Your choice. In practice, if the matrix is sparse, then the ragged array approach is used.

The others are known from intuition and experience.
For example, (1) two P will not teach the same C in the same R in the same T. However, this constraint is overly complicated (requiring all four variables). A shorter constraint could be that two P will not teach in the same R in the same T. This latter constraint has only 3 variables; yet it covers (1) as well as other constraints.
0

Author Comment

ID: 34129618
I think this problem doesn't mean for us to consider how long courses run, actually.
0

LVL 32

Expert Comment

ID: 34129633
I'll be back tomorrow, but will try to respond in a few hours if I have a moment. For now, I'd like you to think more about:

>> Do you think stating "where S = all possible solutions" would work?
>> Yes
Looking at the definition of S as a set of point in U subject to constraints, I think the answer may be No.

>> What do you mean by "|U| = i*j*k*m"?
Sorry, with latest notation, |U| = np * nc * nr * nt = # elements in U
0

LVL 32

Expert Comment

ID: 34129814
>> can C3, for example, appear more than once
>> There might be more than one professor teaching math.
Well, if math-101 is going to be taught twice, then we could define the classes to be unique with a UID for the class; or just names like math-101-class1, math-101-class2 so that every class is distinct. Then we could say that only a class C3 appears only once. Just sound-boarding this if you think this makes the constraints easier to manage. This is your call.
0

LVL 32

Accepted Solution

phoffric earned 2000 total points
ID: 34129828
>> I think it would be good to use two time slot variables: something like - P_A and P_B are in conflicting time slots if the time from T1_A to T2_A and T1_B to T2_B overlap

From OP:
>> a list of possible time slots
D_3 = {T1, ... T_nt}, where nt = # timeslots
A timeslot needs to have an attribute of Start_Time. A second attribute could be either Stop_time or Duration. In either case, I am not understanding the need for two time slot variables, since from the values in D_3, one can compute whether two values overlap.

Also, should we assume that a class attribute to be included is number hours per week, and that all that is necessary is to assure that a class gets the proper number of hours in the set of timeslots allocated to the class?
0

LVL 32

Expert Comment

ID: 34129844
>> my computer has hard disk problems
I may be busy on 14-Nov rebuilding my system (and converting RAID 0 to non-RAID). If I cannot give you the assistance you need to finish, it wouldn't be a bad idea to conclude this question after identifying clear definitions of sets and notations, and then ask a related question posting the conclusions here along with the OP in order to continue with the constraints formulation.
0

Author Closing Comment

ID: 34131768
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Computer science students often experience many of the same frustrations when going through their engineering courses. This article presents seven tips I found useful when completing a bachelors and masters degree in computing which I believe may heâ€¦
Looking for a way to avoid searching through large data sets for data that doesn't exist? A Bloom Filter might be what you need. This data structure is a probabilistic filter that allows you to avoid unnecessary searches when you know the data definâ€¦
In this fifth video of the Xpdf series, we discuss and demonstrate the PDFdetach utility, which is able to list and, more importantly, extract attachments that are embedded in PDF files. It does this via a command line interface, making it suitable â€¦
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaacâ€¦
###### Suggested Courses
Course of the Month11 days, 11 hours left to enroll