I'm trying to solve a constraintsatisfaction 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
pythonconstraint ( http://labix.org/pythonconstraint) 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 4tuples 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: ... 3 1722
Steven Bethard wrote:
I'm trying to solve a constraintsatisfaction 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
Steven Bethard a écrit :
I'm trying to solve a constraintsatisfaction 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
pythonconstraint (http://labix.org/pythonconstraint) 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 4tuples 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: ...
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 teacherstudent 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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics 
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 mosthated "table/view is changing,
trigger/function may not see it" error if I tried to write a trigger that
checks the uniqueness of nonnull values upon insert/update.

by: Jeremiah Jacks 
last post by:
I just upgraded to MySQL 4.0.14standard for RedHat Linux and am using =
the
precompiled 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

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

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,

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),
 
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

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

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
)

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

by: marktang 
last post by:
ONU (Optical Network Unit) is one of the key components for providing highspeed 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...

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

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, ZWave, WiFi, 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...

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

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();...

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 LANtoLAN VPNs.
The last exercise I practiced was to create a LANtoLAN 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...

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
 
by: muto222 
last post by:
How can i add a mobile payment intergratation into php mysql website.
 