473,854 Members | 1,500 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

classroom constraint satisfaction problem

I'm trying to solve a constraint-satisfaction problem, and I'm having
some troubles framing my problem in such a way that it can be
efficiently solved.

Basically, I want to build groups of two teachers and four students such
that [1]:

* Students are assigned to exactly one group
* Teachers are assigned to approximately the same number of groups
* Students are not in groups with their homeroom teachers
* Students in each group are from four different homerooms

So given teachers A, B, C, D, E and F and their corresponding students
A1, A2, ... F3, F4, here's a good grouping:

A, B: C1, D1, E1, F1
B, C: A1, D2, E2, F2
C, D: A2, B1, E3, F3
D, E: A3, B2, C2, F4
E, F: A4, B3, C3, D3
F, A: B4, C4, D4, E4
My current solution is to create a constraint satisfaction problem using
python-constraint (http://labix.org/python-constraint) where there are
variables for:

* each student domain: group names
* each group name domain: all pairs of teachers

This works for simple problems, but because most of my constraints have
to iterate over all students and/or all groups, this takes way too long
on my real dataset (which has 300+ students). I thought about trying to
reframe the problem so that there are variables for:

* each group name domain: pairs of teachers X 4-tuples of students

but that seems like it would be generating something like 15^2*300^4
items for the domain, which is clearly also going to be way too big.
Any suggestions on how to speed things up? I've posted my current code_
and the tests_ in case anyone has the time to look at them.

... _code: http://ucsu.colorado.edu/~bethard/py...dent_groups.py
... _tests:
http://ucsu.colorado.edu/~bethard/py...dent_groups.py
Thanks!

Steve
[1] There are actually two other constraints that I omitted:

* Some teachers cannot be placed in the same group, e.g. I might know
that A cannot work with B or that E cannot work with F.

* If you create a graph out of the teacher pairs from all the groups,
the graph should not be disconnected. That is, the following grouping
is bad because the teachers are disconnected:

A, B: ...
C, D: ...
A, B: ...

while this grouping would be okay:

A, B: ...
B, C: ...
C, D: ...
Oct 15 '06 #1
3 1722
Steven Bethard wrote:
I'm trying to solve a constraint-satisfaction problem, and I'm having
some troubles framing my problem in such a way that it can be
efficiently solved.

Basically, I want to build groups of two teachers and four students such
that [1]:

* Students are assigned to exactly one group
* Teachers are assigned to approximately the same number of groups
* Students are not in groups with their homeroom teachers
* Students in each group are from four different homerooms

So given teachers A, B, C, D, E and F and their corresponding students
A1, A2, ... F3, F4, here's a good grouping:

A, B: C1, D1, E1, F1
B, C: A1, D2, E2, F2
C, D: A2, B1, E3, F3
D, E: A3, B2, C2, F4
E, F: A4, B3, C3, D3
F, A: B4, C4, D4, E4
[snip]
[1] There are actually two other constraints that I omitted:

* Some teachers cannot be placed in the same group, e.g. I might know
that A cannot work with B or that E cannot work with F.

* If you create a graph out of the teacher pairs from all the groups,
the graph should not be disconnected. That is, the following grouping
is bad because the teachers are disconnected:
I would do it in two steps.

Step 1: Generate a graph of all teachers, such that there is one
connection for every four students, and each teacher has approximately
equal number of connections. A simple, approximate way to do this
would be to generate random subsets of two teachers until you have
enough connections (though that won't work well if you have a lot of
teachers that can't work together, which wouldn't be surprising). I'm
sure graph theory has some algorithms to do this if you need more
exactitude.

Step 2: Assign students from appropriate homerooms to each connection.
The following simple algorithm is probably satisfactory: for each
connection between teachers, choose a random subset of four homerooms
not governed by those teachers to form a group. Assign a random
student from each homeroom. Once every student from a homeroom has
been been assigned, remove that homeroom from the set of available
homerooms. With this method, you might have some connections at the
end without enough remaining homerooms; just go fishing for a suitable
switch among students already assigned. Or, work out a way to make
sure you don't exhaust too many homerooms. Perhaps there is a known
algorithm for doing this.

Carl Banks

Oct 15 '06 #2

Steven Bethard a écrit :
I'm trying to solve a constraint-satisfaction problem, and I'm having
some troubles framing my problem in such a way that it can be
efficiently solved.

Basically, I want to build groups of two teachers and four students such
that [1]:

* Students are assigned to exactly one group
* Teachers are assigned to approximately the same number of groups
* Students are not in groups with their homeroom teachers
* Students in each group are from four different homerooms

So given teachers A, B, C, D, E and F and their corresponding students
A1, A2, ... F3, F4, here's a good grouping:

A, B: C1, D1, E1, F1
B, C: A1, D2, E2, F2
C, D: A2, B1, E3, F3
D, E: A3, B2, C2, F4
E, F: A4, B3, C3, D3
F, A: B4, C4, D4, E4
My current solution is to create a constraint satisfaction problem using
python-constraint (http://labix.org/python-constraint) where there are
Last time I looked at it, it seemed to not use (by default) its Arc8
routine that prunes domains between each variable instantiation by the
backtracker. Did you enable it ? (it should have a crucial performance
impact).

You could also try the logilab constraint package
(http://www.logilab.org/projects/constraint) and see how it fares with
your problem (it 'only' provides the AC3 domain pruning algorithm but
at least uses it by default).

Cheers,
Aurélien.
variables for:

* each student domain: group names
* each group name domain: all pairs of teachers

This works for simple problems, but because most of my constraints have
to iterate over all students and/or all groups, this takes way too long
on my real dataset (which has 300+ students). I thought about trying to
reframe the problem so that there are variables for:

* each group name domain: pairs of teachers X 4-tuples of students

but that seems like it would be generating something like 15^2*300^4
items for the domain, which is clearly also going to be way too big.
Any suggestions on how to speed things up? I've posted my current code_
and the tests_ in case anyone has the time to look at them.

.. _code: http://ucsu.colorado.edu/~bethard/py...dent_groups.py
.. _tests:
http://ucsu.colorado.edu/~bethard/py...dent_groups.py
Thanks!

Steve
[1] There are actually two other constraints that I omitted:

* Some teachers cannot be placed in the same group, e.g. I might know
that A cannot work with B or that E cannot work with F.

* If you create a graph out of the teacher pairs from all the groups,
the graph should not be disconnected. That is, the following grouping
is bad because the teachers are disconnected:

A, B: ...
C, D: ...
A, B: ...

while this grouping would be okay:

A, B: ...
B, C: ...
C, D: ...
Oct 16 '06 #3
Carl Banks wrote:
Steven Bethard wrote:
>Basically, I want to build groups of two teachers and four students such
that [1]:

* Students are assigned to exactly one group
* Teachers are assigned to approximately the same number of groups
* Students are not in groups with their homeroom teachers
* Students in each group are from four different homerooms

So given teachers A, B, C, D, E and F and their corresponding students
A1, A2, ... F3, F4, here's a good grouping:

A, B: C1, D1, E1, F1
B, C: A1, D2, E2, F2
C, D: A2, B1, E3, F3
D, E: A3, B2, C2, F4
E, F: A4, B3, C3, D3
F, A: B4, C4, D4, E4

[snip]
>[1] There are actually two other constraints that I omitted:

* Some teachers cannot be placed in the same group, e.g. I might know
that A cannot work with B or that E cannot work with F.

* If you create a graph out of the teacher pairs from all the groups,
the graph should not be disconnected. That is, the following grouping
is bad because the teachers are disconnected:

I would do it in two steps.

Step 1: Generate a graph of all teachers, such that there is one
connection for every four students, and each teacher has approximately
equal number of connections. A simple, approximate way to do this
would be to generate random subsets of two teachers until you have
enough connections (though that won't work well if you have a lot of
teachers that can't work together, which wouldn't be surprising). I'm
sure graph theory has some algorithms to do this if you need more
exactitude.

Step 2: Assign students from appropriate homerooms to each connection.
The following simple algorithm is probably satisfactory: for each
connection between teachers, choose a random subset of four homerooms
not governed by those teachers to form a group. Assign a random
student from each homeroom. Once every student from a homeroom has
been been assigned, remove that homeroom from the set of available
homerooms. With this method, you might have some connections at the
end without enough remaining homerooms; just go fishing for a suitable
switch among students already assigned. Or, work out a way to make
sure you don't exhaust too many homerooms. Perhaps there is a known
algorithm for doing this.
For what it's worth, I went basically this route. My code does
something like:

(1) Generate all pairs of teachers

(2) Remove any pairs of teachers in conflict

(3) Create a list for teacher pairs

(4) Randomly select a teacher pair and add it to the list

(5) If any teachers are at their max number of groups, remove all pairs
that include them from the pairs we are randomly selecting from

(6) If we have not selected a teacher pair for each group, goto (4)

(7) If the resulting graph is disconnected, try again from step (3)

(8) We now have one pair of teachers for each group

(8) Randomly select four other teachers' homerooms for each group

(9) Randomly pop a student off of each homeroom and add it to the group

(10) If a homeroom becomes empty, remove it from the homerooms we are
randomly selecting from.

(11) If at any point we run out of students, try again from step (3)

(12) Eventually, we have assigned people to all teacher-student groups

This seems to work pretty quickly, and doesn't have much trouble finding
solutions to the datasets I've tried it on.

Thanks for your help!

Steve
Oct 23 '06 #4

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

26
45465
by: Agoston Bejo | last post by:
I want to enforce such a constraint on a column that would ensure that the values be all unique, but this wouldn't apply to NULL values. (I.e. there may be more than one NULL value in the column.) How can I achieve this? I suppose I would get the most-hated "table/view is changing, trigger/function may not see it" error if I tried to write a trigger that checks the uniqueness of non-null values upon insert/update.
0
2641
by: Jeremiah Jacks | last post by:
I just upgraded to MySQL 4.0.14-standard for RedHat Linux and am using = the pre-compiled binaries. I have a database with INNODB tables. When I insert a row into one of the child tables, I get the following = MySQL error: INSERT INTO product_access_level (product_id,access_level_id) VALUES
4
2921
by: wireless | last post by:
I've written code that dynamically builds an sql query based on various constraint possibilities. The problem is the code would have been very complex had I not come up with a dummy constraint as a kind of place holder in the statement. To avoid complex logic that determines if there was another constraint before any other constraint and hence the need to add, say, AND or not, I came up with a dummy constraint so that every subsequent...
0
1848
by: Fabre Lambeau | last post by:
I've got a problem when adding a CONSTRAINT CHECK on a table by calling a function. It just seems not to work... Here is the table (simplified to only the relevant fields for this case): CREATE TABLE public.tb_contacts ( contact_id serial NOT NULL, actor_id varchar(50) NOT NULL, contacttype_id varchar(6) NOT NULL,
2
10139
by: yongsing | last post by:
I have two tables as shown below (only relevant columns shown). The second table is dependent on the first one. CREATE TABLE PARENTTABLE ( ... SERIAL CHAR(12) NOT NULL, ENDDATE TIMESTAMP NOT NULL, PKLINK INTEGER GENERATED ALWAYS AS IDENTITY (START WITH -2147483648, INCREMENT BY 1), PRIMARY KEY (PKLINK),
1
3832
by: | last post by:
Hi, I am getting the following error when I run my Visual Basic application: "Cannot add primary key constraint since primary key is already set for the table" I am using datasets with primary keys which are filled from an SQL Server database. These datasets were automatically
2
6570
by: D. Dante Lorenso | last post by:
I'm trying to build a table that will store a history of records by enumerating the records. I want the newest record to always be number ZERO, so I created a trigger on my table to handle the assignment of version numbers: CREATE TRIGGER "trg_audio_file_insert" BEFORE INSERT ON "public"."audio_file" FOR EACH ROW EXECUTE PROCEDURE "public"."trg_audio_file_insert"(); My trigger function looks like this...
15
8599
by: Frank Swarbrick | last post by:
I have the following three tables DROP TABLE CALLTRAK.SERVICE_CODES @ CREATE TABLE CALLTRAK.SERVICE_CODES ( CODE CHAR(1) NOT NULL , CONSTRAINT SERVICE_CODES_PK PRIMARY KEY (CODE) , DESCRIPTION VARCHAR(50) NOT NULL )
2
15094
by: rorajoey | last post by:
Violation of UNIQUE KEY constraint 'IX_surveyQuestions'. Cannot insert duplicate key in object 'dbo.surveyQuestions'. This might seem like a simple matter of trying to insert a row with ID=20 when there's already one with that ID, but the problem is a bit more complicated. The table is supposed to auto-increment the value for the primary key when a new record is inserted. But no matter what I do, I can't seem to insert more than one record...
0
9901
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
10675
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
10749
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
10367
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
1
7912
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
7079
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
5740
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
1
4556
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
4152
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.